COMMENT ⊗   VALID 00019 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	%folio 802 galley 1a (C) Addison-Wesley 1978	-
C00014 00003	%folio 804 galley 1b (C) Addison-Wesley 1978	-
C00019 00004	%folio 805 galley 2 (C) Addison-Wesley 1978	-
C00028 00005	%folio 810 galley 3 (C) Addison-Wesley 1978	-
C00046 00006	%folio 818 galley 4a (C) Addison-Wesley 1978	-
C00053 00007	%folio 819 galley 4b (C) Addison-Wesley 1978	-
C00065 00008	%folio 821 galley 5 (C) Addison-Wesley 1978	-
C00080 00009	%folio 824 galley 6a (C) Addison-Wesley 1978	-
C00089 00010	%folio 826 galley 6b (C) Addison-Wesley 1978	-
C00096 00011	%folio 828 galley 7 (C) Addison-Wesley 1978	-
C00112 00012	%folio 832 galley 8 (C) Addison-Wesley 1978	-
C00129 00013	%folio 835 galley 9a (C) Addison-Wesley 1978	-
C00141 00014	%folio 840 galley 9b (C) Addison-Wesley 1978
C00146 00015	%folio 842 galley 10 (C) Addison-Wesley 1978
C00157 00016	%folio 844 galley 11 "special italic figs in position 4" (C) Addison-Wesley 1978
C00170 00017	%folio 845 galley 12 (C) Addison-Wesley 1978
C00184 00018	%folio 849 galley 13 (C) Addison-Wesley 1978
C00193 00019	
C00194 ENDMK
C⊗;
%folio 802 galley 1a (C) Addison-Wesley 1978	-
|newtype W58320---Computer Programming\quad (Knuth/Addison-Wesley)\quad
Answers\quad f. 802\quad g. 1d
$$\qquad This extension of Euclid's algorithm includes most
of the features we have seen in previous extensions, all at
the same time, so it provides new insight into the special cases
already considered. To prove that it is valid, note first that
deg($v↓2)$ decreases in step C4, so the algorithm certainly
terminates. At the conclusion of the algorithm, $v↓1$ is a common
right divisor of $V↓1$ and $V↓2$, since $w↓1v↓1 = (-1)↑nV↓1$
and $-w↓2v↓1 = (-1)↑nV↓2$; also if $d$ is any common right divisor
of $V↓1$ and $V↓2$, it is a right divisor of $z↓1V↓1 + z↓2V↓2
= v↓1$. Hence $v↓1 =$ gerd($V↓1, V↓2)$. Also if $m$ is any common
left multiple of $V↓1$ and $V↓2$, we may assume without loss
of generality that $m = U↓1V↓1 = U↓2V↓2$, since the sequence
of values of $Q$ does not depend on $U↓1$ and $U↓2$. Hence $m
= (-1)↑n(-u↓2z↑\prime↓{1})V↓1 = (-1)↑n(u↓2z↑\prime↓{2})V↓2$
is a multiple of $z↑\prime↓{1}V↓1$.

In practice, if we just want to calculate gerd($V↓1,
V↓2)$, we may suppress the computation of $n, w↓1, w↓2, w↑\prime↓{1},
w↑\prime↓{2}, z↓1, z↓2, z↑\prime↓{1}, z↑\prime↓{2}$;
These additional quantities were added to the algorithm primarily
to make its validity more readily established.

${\sl Note:}$ Nontrivial factorizations of string
polynomials, such as the example given with this exercise, can
be found from matrix identities such as
$$\left(${a\qquad \atop 1\qquad 0}$}\left(${b\qquad 1\atop 1\qquad
0}$}\left(${c\qquad 1\atop 1\qquad 0}$}\left(${0\qquad 1\atop
1\quad -c}$}\left(${0\qquad 1\atop 1\quad -b}$}\left(${0\qquad
1\atop 1\quad -a}$} = \left(${1\qquad 0\atop 0\qquad 1}$},
|qctr \9skip that hold even when multiplication is not commutative.
For example,
$$$(abc + a + c)(1 + ba) = (ab + 1)(cba + a + c)$.
|qctr \9skip ((Compare this with the ``continuant polynomials''
of Section 4.5.3.)

\ansno 19. (Solution by Michael Fredman.) If such an algorithm
exists, $D$ is a gerd by the argument in exercise 18. Let us
regard $A$ and $B$ as a single $2n \times n$ matrix $C$ whose
first $n$ rows are those of $A$, and whose second $n$ rows are
those of $B$. Similarly, $P$ and $Q$ can be combined into a
$2n \times n$ matrix $R; X$ and $Y$ can be combined into an
$n \times 2n$ matrix $Z:$ the desired conditions now reduce
to two equations $C = RD, D = ZC$. If we can find a $2n \times
2n$ integer matrix $U$ of determinant \pm 1 such that the last
$n$ rows of $U↑{-1}C$ are all zero, then $R =$ (first $n$ columns
of $U), D =$ (first $n$ rows of $U↑{-1}C), Z =$ (first $n$ rows
of $U↑{-1})$ solves the desired conditions. Hence, for example,
the following triangularization algorithm may be used $(m =
2n):$

\algbegin Algorithm T. Let $C$ be an $m \times n$ matrix
of integers. This algorithm finds $m \times m$ integer matrices
$U$ and $V$ such that $UV = I$ and $VC$ is ``upper triangular.''
(The entry in row $i$ and column $j$ of $VC$ is zero if $i >
j.)$

\algstep T1. [Initialize.] Set $U ← V ← I$, the
$m \times m$ identity matrix; and set $T ← C$.\xskip (Throughout the
algorithm we will have $T = VC, UV = 1.)$

\algstep T2. [Iterate on $j$.] Do step T3 for $j = 1$, 2, $\ldotss
$, min($m, n)$, and terminate the algorithm.

\algstep T3. [Zero out column $j$.] Perform the following transformation
zero or more times until $T↓{ij}$ is zero for all $i > j$: Let
$T↓{kj}$ be a nonzero element of \{$T↓{ij}, T↓{(j+1)j}, \ldotss$,
$T↓{mj}\}$ having the smallest absolute value. Interchange
rows $k$ and $j$ of $T$ and of $V$; interchange columns $k$
and $j$ of $U$. Then subtract \lfloor $T↓{ij}/T↓{jj}\rfloor$
times row $j$ from row $i$, in matrices $T$ and $V$, and add
the same multiple of column $i$ to column $j$ in matrix $U$,
for $j < i ≤ m$.

|qleft \3skip |cancelindent \qquad For the stated example, the
algorithm yields $({1\qquad 2\atop 3\qquad 4}$) =$ ({1\qquad
0\atop 3\qquad 2}$)(${1\qquad 2\atop 0\quad -1}$),$ ({4\qquad
3\atop 2\qquad 1}$) = (${4\qquad 5\atop 2\qquad 3}$)(${1\qquad
2\atop 0\quad -1}$), (${1\qquad 2\atop 0 \quad -1}$) = (${1\qquad
0\atop 2\quad -2}$)(${1\qquad 2\atop 3\qquad 4}$) + (${0\qquad
0\atop 1\qquad 0}$)(${4\qquad 3\atop 2\qquad 1}$).\xskip (Actually
any matrix with determinant \pm 1 would be a gcrd in this case.)

\ansno 20. It may be helpful to consider exercise 4.6.2--22
with $p↑m$ replaced by a small number $ε$.

\ansno 21. Note that Algorithm R is used only when $m - n ≤
1$, and that the coefficients are bounded by (25) with $m =
n. [$The stated formula is, in fact, the execution time observed
in practice, not merely an upper bound. For more detailed information
see G. E. Collins, {\sl Proc. {\sl 1968 }Summer Inst.\ on Symbolic
Math.\ Comp.}, Robert G. Tobey, ed.\ (IBM Federal Systems Center,
June 1969), 195--231.]

\ansno 22. A sequence of signs cannot contain two consecutive
zeros, since $u↓{k+1}(x)$ is a nonzero constant in (28). Moreover
we cannot have +, 0, + or -, 0, - as subsequences. The formula
$V(u, a) - V(u, b)$ is clearly valid when $b = a$, so we must
only verify it as $b$ increases. The polynomials $u↓j(x)$ have
finitely many roots, and $V(u, b)$ changes only when $b$ encounters
or passes such roots. Let $x$ be a root of some (possibly several)
$u↓j$. When $b$ increases from $x - ε$ to $x$, the sign sequence
near $j$ goes from +, \pm , - to +, 0, - or from -, \pm , +
to -, 0, + if $j > 0$; and from +, - to 0, - or from -, + to
0, + if $j = 0$.\xskip (Since $u↑\prime (x)$ is the derivative, $u↑\prime
(x)$ is negative when $u(x)$ is decreasing.) Thus the net change
in $V$ is $-\delta ↓{j0}$. When $b$ increases from $x$ to $x
+ ε$, a similar argument shows that $V$ remains unchanged.

[L. E. Heindel, {\sl JACM} {\bf 18} (1971), 533--548,
has applied these ideas to construct algorithms for isolating
the real zeroes of a given polynomial $u(x)$, in time bounded
by a polynomial in deg($u)$ and log $N$, where all coefficients
$y↓j$ are integers with |$u↓j| ≤ N$, and all operations are
guaranteed to be exact.]

\ansno 23. If $v$ has $n - 1$ real roots occurring between the
$n$ real roots of $u$, then (by considering sign changes) $u(x)$mod
$v(x)$ has $n - 2$ real roots lying between the $n - 1$ of $v$.

%folio 804 galley 1b (C) Addison-Wesley 1978	-
|qleft \24skip |newtype {\:r SECTION 4.6.2

\ansno 1. By the principle of inclusion
and exclusion (Section 1.3.3), the number of polynomials without
linear factors is \sum $↓{k≤n} ({p\atop k)p↑{n-k}(-1)↑k = p↑{n-p}(p
- 1)↑p$. The stated probability is therefore 1 - (1 - 1/$p)↑p$,
which is greater than ${1\over 2}$; in fact, it is greater than
${1\over 2}$ for all $n ≥ 1$.

\ansno 2. (a) We know that $u(x)$ has a representation
as a product of irreducible polynomials, and the leading coefficients
of these polynomials must be units, since they divide the leading
coefficient of $u(x)$. Therefore we may assume that $u(x)$ has
a representation as a product of monic irreducible polynomials
$p↓1(x)↑e|infsup 1 \ldotsm p↓r(x)↑e|infsup r$, where $p↓1(x),
\ldotss , p↓r(x)$ are distinct. This representation is unique,
except for the order of the factors, so the conditions on $u(x),
v(x), w(x)$ are satisfied if and only if
$$$v(x) = p↓1(x)↑|"l↑e|infsup 1↑{/2|}"L \ldotsm p↓r(x)↑|"l↑e|infsup
r↑{/2}\rfloor , w(x) = p↓1(x)↑e|infsup 1$$↑{mod2} \ldotsm p↓r(x)↑e|infsup
r$$↑{mod2}$.

(b) The generating function for the number
of monic polynomials of degree $n$ is $1 + pz + p↑2z↑2 + \cdots
= 1/(1 - pz)$. The generating function for the number of polynomials
of degree $n$ having the form $v(x)↑2$, where $v(x)$ is monic,
is 1 + $pz↑2 + p↑2z↑4 + \cdots = 1/(1 - pz↑2)$. If the generating
function for the number of monic squarefree polynomials of degree
$n$ is $g(z)$, then by part (a) 1/(1 - $pz) = g(z)/(1 - pz↑2)$.
Hence $g(z) = (1 - pz↑2)/(1 - pz) = 1 + pz + (p↑2 - p)z↑2 +
(p↑3 - p↑2)z↑3 + \cdotss$. The answer is $p↑n - p↑{n-1}$ for
$n ≥ 2$.\xskip (Curiously, this proves that gcd\biglp $u(x), u↑\prime
(x)\bigrp =$ 1 with probability 1 - 1/$p$; it is the sameas
the probability that gcd(\biglp $u(x), v(x)\bigrp = 1$ if $u(x)$
and $v(x)$ are {\sl independent}, by exercise 4.6.1--5.)

\ansno 3. Let $u(x) = u↓1(x) \ldotsm u↓r(x)$. There is {\sl at
most} one such $v(x)$, by the argument of Theorem 4.3.2C\null. There
is {\sl at least} one if, for each $j$, we can solve the system
with $w↓j(x) = 1$ and $w↓k(x) = 0$ for $k ≠ j$. A solution to
the latter is $v↓1(x) ??7↓k|spose ↓|↔6↓{=j} u↓k(x)$, where $v↓1(x)$
and $v↓2(x)$ can be found satisfying
$$$v↓1(x) ??7↓k|spose ↓|↔6↓{=j} u↓k(x) + v↓2(x)u↓j(x) = 1,\qquad$
deg($v↓1) <$ deg($u↓j)$,
|qctr \9skip by the extension of Euclid's algorithm (exercise
4.6.1--3).

|qleft \1skip a??U31}TEAM 1
|qleft |newtype W58320---
%folio 805 galley 2 (C) Addison-Wesley 1978	-
πComputer Programming (Knuth/Addison-Wesley) Answers f. 805
g. 2d
\ansno 4. The unique factorization theorem gives the identity
($1 - pz)↑{-1} = ??7↓{n≥1} (1 - z↑n)↑{-a}|infsup n|infsup p$;
after taking logarithms, this can be rewritten \sum ↓{j≥1} G$↓p(z↑j)/j
= \sum ↓{k,j≥1} a↓{kp}z↑{kj}/j =$ ln\biglp 1/(1 - pz)\bigrp
. The stated identity now yields the answer $G↓p(z) = \sum ↓{m≥1}
\mu (m)m↑{-1}$ ln\biglp 1/(1 - pz$↑m)\bigrp $, from which we
obtain $a↓{np} = \sum ↓{d\rslash n} \mu (n/d)n↑{-1}p↑d$; lim↓{$p→∞}
a↓{np}/p↑n = 1/n$. To prove the stated idnetity, note that \sum
↓{$n,j≥1 \mu (n)g(z↑{nj})n↑{-t}j↑{-t} = \sum ↓{m≥1} g(z↑m)m↑{-t}
\sum ↓{n\rslash m} \mu (n) = g(z)$.

\ansno 5. Let $a↓{npr}$ be the number of monic
polynomials of degree $n$ modulo $p$ having exactly $r$ irreducible
factors. Then $??G↓p(z, w) = \sum ↓{n,r≥0} a↓{npr}z↑nw↑r =$
exp\biglp $\sum ↓{k≥1} G↓p(z↑k)w↑k/k\bigrp $; cf.\ Eq.\ 1.2.9--34.
We have \sum ↓{$n≥0} A↓{np}z↑n = d??G↓p(z/p, w)/dw ,↓{w=1} =
\biglp \sum ↓{k≥1}G↓p(|newtype z↑k/p↑k)\bigrp$ exp\biglp ln(1/(1
- $z))\bigrp = (\sum ↓{n≥1}$ ln\biglp 1/(1 - $p↑{1-n}z↑n))\varphi
(n)/n)/z\bigrp $, hence $A↓{np} = H↓n + 1/2p + O(p↑{-2})$ for
$n ≥ 2$. The average value of $2↑r$ is the coefficient of $z↑n$
in $??G↓p(z/p, 2)$, namely $n + 1 + (n + 1)/p + O(p↑{-2})$.\xskip (The
variance is of order $n↑3$, however: set $w = 4.)$

\ansno 6. For $0 ≤ s < p, x - s$ is a factor of
$x↑p - x$ (modulo $p)$ by Fermat's theorem. So $x↑p - x$ is
a multiple of lcm\biglp $x - 0, x - 1, \ldotss , x - (p - 1)|raiseordrop
)|newtype = x↑p. (Note{\sl : }$Therefore the Stirling numbers
[${p\atop k}]$ are multiples of $p$ except when $k = 1, k =
p$. Equation 1.2.6--41 shows that the same statement is valid
for Stirling numbers \in${p\atop k}↑\prime$ of the other kind.)

\ansno 7. The factors on the right are relatively
prime, and each is a divisor of $u(x)$, so their product divides
$u(x)$. On the other hand,
$$$u(x)\qquad$ divides\qquad $v(x)↑p - v(x) = \prod ↓{0≤s<p}
\biglp v(x) - s\bigrp $,
|qctr \6skip so it divides the right-hand side by exercise 4.5.2--2.

\ansno 8. The vector that is output in step N3
is the only output whose $k$th component is nonzero.

\ansno 9. For example, start with $x ← 1, y ← 1$;
then repeatedly set {\sl R[x] ← y, x ←2x} mod 101, $y ← 51y$
mod 101, one hundred times.

\ansno 10. The matrix $Q - I$ below has a null space generated
by the two vectors $v↑{[1]} =(1, 0, 0, 0, 0, 0, 0, 0), v↑{[2]}
= (0, 1, 1, 0, 0, 1, 1, 1)$. The factorization is
$$($x↑6 + x↑5 + x↑4 + x + 1)(x↑2 + x + 1)$.
|qctr \6skip |newtype |tab \qquad \qquad |tab \qquad \qquad
\qquad \qquad \qquad \qquad \qquad \qquad \qquad |tab \qquad
\qquad \qquad |tab \qquad \qquad \qquad \qquad \qquad \qquad
\qquad \quad |tab \qquad \qquad |tab |zfa ⊗⊗$p = 2⊗⊗p = 5\cr
\6skip \qquad \qquad 0\qquad 0\qquad 0\qquad 0\qquad 0\qquad
0\qquad 0\qquad 0\qquad \qquad \qquad 0\qquad 0\qquad 0\qquad
0\qquad 0\qquad 0\qquad 0$

\qquad 0\qquad 1\qquad 1\qquad 0\qquad 0\qquad
0\qquad 0\qquad 0\qquad \qquad \qquad 0\qquad 4\qquad 0\qquad
0\qquad 0\qquad 1\qquad 0
\qquad 0\qquad 0\qquad 1\qquad 0\qquad 1\qquad
0\qquad 0\qquad 0\qquad \qquad \qquad 0\qquad 2\qquad 2\qquad
0\qquad 4\qquad 3\qquad 4
\qquad 0\qquad 0\qquad 0\qquad 1\qquad 0\qquad
0\qquad 1\qquad 0\qquad \qquad \qquad 0\qquad 1\qquad 4\qquad
4\qquad 4\qquad 2\qquad 1
\qquad 1\qquad 0\qquad 0\qquad 1\qquad 0\qquad
0\qquad 1\qquad 0\qquad \qquad \qquad 2\qquad 2\qquad 2\qquad
3\qquad 4\qquad 3\qquad 2

\qquad 1\qquad 0\qquad 1\qquad 1\qquad 1\qquad
0\qquad 0\qquad 0\qquad \qquad \qquad 0\qquad 0\qquad 4\qquad
0\qquad 1\qquad 3\qquad 2

\qquad 0\qquad 0\qquad 1\qquad 0\qquad 1\qquad
1\qquad 0\qquad 1\qquad \qquad \qquad 3\qquad 0\qquad 2\qquad
1\qquad 4\qquad 2\qquad 1

\qquad 1\qquad 1\qquad 0\qquad 1\qquad 1\qquad
1\qquad 0\qquad 1

\ansno 11. Removing the trivial factor
$x$, the matrix $Q - I$ above has a null space generated by
(1, 0, 0, 0, 0, 0, 0) and (0, 3, 1, 4, 1, 2, 1). The factorization
is
$$$x(x↑2 + 3x + 4)(x↑5 + 2x↑4 + x↑3 + rx↑2 + x + 3)$.

\ansno 12. If $p = 2, (x + 1)↑4 = x↑4 + 1$. If $p
= 8k + 1, Q - I$ is the zero matrix, so there are four factors.
For other values of $p$ we have
$$|newtype \qquad \qquad \qquad \qquad $p = 8k + 3\qquad \qquad
p = 8k + 5\qquad \qquad p = 8k + 7$

|qleft \6skip ??M32}0\qquad 0\qquad 0\qquad 0\quad 0\qquad 0\qquad
0\qquad 0\quad 0\qquad 0\qquad 0\qquad 0

|qleft \6skip $Q - I = \-6skip 0\qquad -1\qquad 0\qquad 1\quad
0\qquad -2\qquad 0\qquad 0\quad 0\qquad -1\qquad 0\qquad -1$
|qleft 0\qquad 0\qquad -2\qquad 0\quad 0\qquad 0\qquad 0\qquad
0\quad 0\qquad 0\qquad -2\qquad 0
|qleft Q - I = 0\qquad 1\qquad 0\qquad -1\quad 0\qquad 0\qquad
0\qquad -2\quad 0\qquad -1\qquad 0\qquad -1

|qleft \6skip ??M29}Here $Q - I$ has rank 2, so there are 4
- 2 = 2 factors. (But it is easy to prove that $x↑4 + 1$ is
irreducible over the integers, since it has no linear factors
and the coefficient of $x$ in any factor of degree two must
be less than or equal to 2 in absolute value by exercise 20.
For all $k ≥ 2$, H. P. F. Swinnerton-Dyer has exhibited polynomials
of degree $2↑k$ that are irreducible over the integers, but
they split completely into linear and quadratic factors modulo
every prime. For degree 8, his example is $x↑8 - 16x↑6 + 88x↑4
+192x↑2 + 144$, having roots $|newtype$ W58320---Computer
%folio 810 galley 3 (C) Addison-Wesley 1978	-
\ansno 16. (a) Substitute polynomials modulo $p$ for integers,
in the proof for $n = 1$.\xskip (b) The proof for $n=1$
carries over to any finite field.\xskip (c) Since $x = \xi ↑k$ for
some $k$, $x↑{p↑n} = x$ in the field defined by $f(x)$. Furthermore, the elements
$y$ that satisfy the equation $y↑{p↑m} = y$ in the field
are closed under addition, and closed under multiplication;
so if $x↑{p↑m}= x$, then $\xi$ (being a polynomial in
$x$ with integer coefficients) satisfies $\xi↑{p↑m} =
\xi $.

\ansno 17. If $\xi$ is a primitive root, each nonzero element
is some power of $\xi $. Hence the order must be a divisor of
13$↑2 - 1 = 2↑3 \cdot 3 \cdot 7, and \varphi (f)$ elements have
order $f$.

|qleft \6skip |tab \qquad |tab \qquad \quad |tab \qquad \quad
|tab \qquad \quad |tab \qquad \quad |tab \qquad \quad |tab \qquad
\quad |tab \qquad \quad |tab |zfa ⊗f⊗\varphi (f)⊗f⊗\varphi (f)⊗f⊗\varphi
(f)⊗f⊗\varphi (f)\cr
\2skip 1⊗1⊗ 3⊗2⊗ 7⊗ 6⊗ 21⊗12\cr
2⊗1⊗ 6⊗2⊗14⊗ 6⊗ 42⊗12\cr
4⊗2⊗12⊗4⊗28⊗12⊗ 84⊗24\cr
8⊗4⊗24⊗8⊗56⊗24⊗168⊗48\cr

\ansno 18. (a) pp\biglp $p↓1(u↓nx)\bigrp \ldotsm$
pp\biglp $p↓r(u↓nx)\bigrp $, by Gauss's lemma. For example,
let
$$$u(x) = 6x↑3 - 3x↑2 + 2x - 1,\qquad v(x) = x↑3 - 3x↑2 + 12x
- 36 = (x↑2 + 12)(x - 3)$;
|qctr \9skip then pp($36x↑2 + 12) = 3x↑2 + 1$, pp($6x - 3) =
2x - 1$.\xskip (This is a modern version of a fourteenth-century trick
used for many years to help solve algebraic equations.)

(b) Let pp\biglp $w(u↓nx)\bigrp = |spose 3w↓mx↑m
+ \cdots + |spose 3w↓0 = w(u↓nx)/c$, where $c$ is the content
of $w(u↓nx)$ as a polynomial in $x$. Then $w(x) = (c|spose 3w↓m/u↑{m}↓{n}
+ \cdots + c|spose 3w↓0$, hence $c|spose 3w↓m = u↑{m}↓{n}$;
since $|spose 3w↓m$ is a divisor of $u↓n, c$ is a multiple of
$u↑{m-1}↓{n}$.
|qleft u?????U31}TEAM 1
|qleft |newtype W58320---Comput

\ansno 19. If $u(x) = v(x)w(x)$ with deg($v)$deg($w) ≥
1$, then $u↓nX↑n ≡ v(x)w(x) \modulo p$. By unique factorization
modulo $p$, all but the\3skip {

\ansno 20. (a) $\sum (αu↓j - u↓{j-1})(|spose
3α|spose 3u↓j - |spose 3u↓{j-1}) = \sum (u↓j - |spose 3αu↓{j-1})(|spose
3u↓j - α|spose 3u↓↓1)$.\xskip (b) We may assume that $u↓0 ≠ 0$. Let
$m(u) = ??7↓{1≤j≤n}$ min($1, |α↓j|) = u↓0/M(u)u↓n$. Whenever
|$α↓j| < 1$, change the factor $x - α↓j$ to $|spose 3α↓jx -
1$ in $u(x)$; this doesn't affect $|u|$. Now looking at the
leading and trailing coefficients only, we have $|u|↑2 ≥ |u↓n|↑2m(u)↑2
+ |u↓n|↑2M(u)↑2$; hence we obtain the slightly stronger result
$M(u)↑2 ≤ \biglp |u|↑2 + (|u|↑4 - 4|u↓0u↓n|↑2)↑|f1??32??\bigrp
/2|u↓n|↑2$.\xskip (c) $u↓j = u↓m \sum α↓i|infinf 1 \ldotsm α↓i|infinf
m|infinf -|infinf j$, an elementary symmetric function, hence
$u↓j| ≤ |u↓m| \sum β↓i|infinf 1 \ldotsm β↓i|infinf m|infinf -|infinf
j$ where $β↓i =$ max(1, $|α↓i|)$. We complete the proof by showing
that when 1 ≤ $x↓1, \ldotss , x↓n$ and $x↓1 \ldotsm x↓n = M$,
the elementary symmetric function $\sigma ↓{nk} = \sum x↓i|infinf
1 \ldotsm x↓i|infinf k$ is ≤(${n-1\atop k-1})M + ({n-1\atop k})$,
the value assumed when $x↓1 = \cdots = x↓{n-1} = 1$ and $x↓n
= M$.\xskip (For if $x↓1 ≤ \cdots ≤ x↓n < M$, the transformation $x↓n
← x↓{n-1}x↓n, x↓{n-1} ← 1$ increases $\sigma ↓{nk}$ by $\sigma
↓{(n-2)(k-1)}(x↓n - 1)(x↓{n-1} - 1) > 0.)$\xskip (d) $|v↓j| ≤ |v↓m|\biglp
({m-1\atop j})M(v) + ({m-1\atop j-1})\bigrp ≤ |U↓n|\biglp ({m-1\atop
j})M(u) + ({m-1\atop j-1})\bigrp$ since $|v↓m| ≤ |u↓n|$ and
$M(v) ≤ M(u). [$These results are slight extensions of inequalities
due to M. Mignotte, {\sl Math.\ Comp.\ {bf 28} (1974), 1153--1157.]

\ansno 21. (a) J↑{1}↓{0}$ (u↓ne(n\theta ) + \cdots + u↓0)(|spose
3u↓ne(-n\theta ) + \cdots + |spose 3u↓0) d\theta = |u↓n|↑2 +
\cdots + |u↓0|↑2$ since $\int ↑{1}↓{0} e(j\theta )e(-k\theta
) d\theta = \delta ↓{jk}$; now use induction on $t$.\xskip (b) Since
$|v↓j| ≤ ({m\atop j})M(v)|v↓m|$ we conclude that $|v|↑2 ≤ ({2m\atop
m})M(v)↑2|v↓m|↑2$. Hence $|v|↑2|w|↑2 ≤ ({2m\atop m})({2k\atop
k})M(v)↑2M(w)↑2|v↓mw↓k|↑2 = f(m, k)M(u)↑2|u↓n|↑2 ≤ f(m, k)|u|↑2.
[$Slightly better values for $f(m, k)$ are possible based on
the more detailed information in exercise 20.]\xskip (c) The case
$t = 3$ suffices to show how to get from $t - 1$ to $t$. When
$t = 2$ we have shown that, for all $\theta ↓1, \int ↑{1}↓{0}
\int ↑{1}↓{0} \int ↑{1}↓{0} \int ↑{1}↓{0} |v\biglp e(\theta
↓1), e(\phi ↓2), e(\phi ↓3)\bigrp |↑2 |w\biglp e(\theta ↓1),
e(\psi ↓2), e(\psi ↓3)\bigrp |↑2 d\phi ↓2 d\phi ↓3 d\psi ↓2
d\psi ↓3 ≤ f(m↓2, k↓2)f(m↓3, k↓3) \int ↑{1}↓{0} \int ↑{1}↓{0}
|V\biglp e(\theta ↓1), e(\theta ↓2), e(\theta ↓3)\bigrp |↑2
|w\biglp e(\theta ↓1), e(\theta ↓2), e(\theta ↓3)\bigrp |↑2
d\theta ↓2 d\theta ↓3$. For all $\phi ↓2, \phi ↓3, \psi ↓2,
\psi ↓3$ we have also shown that $\int ↑{1}↓{0} \int ↑{1}↓{0}
|V\biglp e(\phi ↓1), e(\phi ↓2), e(\phi ↓3)\bigrp |↑2 |w\biglp
e(\psi ↓1), e(\psi ↓2), e(\psi ↓3)\bigrp |↑2 d\phi ↓1 d\psi
↓1 ≤ f(m↓1, k↓1) \int ↑{1}↓{0} |v\biglp e(\theta ↓1), e(\phi
↓2), e(\phi ↓3)\bigrp |↑2 |w\biglp e(\theta ↓1), e(\psi ↓2),
e(\psi ↓3)\bigrp |↑2 d\theta ↓1$. Integrate the former inequality
wi7h respect to $\theta ↓1$ and the latter with respect to $\phi
↓2, \phi ↓3, \psi ↓2, \psi ↓3.\xskip [$This method was used by A.
O. Gel'fond in {\sl Transcendental and Algebraic Numbers (}New
York: Dover, 1960), Section 3.4, to derive a slightly different
result.]

\ansno 22. More generally, assume that $u(x) ≡ v(x)w(x)\modulo
q$, $a(x)v(x) + b(x)w(x) ≡ 1 \modulo p$, and $c??3(v) ≡ 1
($modulo $r)$, deg($a) <$ deg($w)$, deg($h) <$ deg($v)$, deg($u)
=$ deg($v) +$ deg($w)$, where $r =$ gcd($p, q)$ and $p, q$ needn't
be prime. We shall construct polynomials $V(x) ≡ v(x)$ and $W(x)
≡ w(x) \modulo q$ such that $u(x) ≡ V(x)W(x) \modulo {qr}$,
??3(V) = ??3(v)$, deg($V) =$ deg($W) =$ deg($w)$; furthermore,
if $r$ is prime, the results will be unique modulo $qr$.

The problem asks us to find $|spose 3v(x)$ and
$|spose 3w(x)$ with $V(x) = v(x) + q|spose 3v(x), \biglp N(x)
= w(x) + q|spose 3w(x)$, deg($|spose 3v) <$ deg($v)$, deg($|spose
3w) ≤$ deg($w)$; and the other condition \biglp $v(x) + q|spose
3v(x)|newtype )(|newtype w(x) + q|spose 3w(x)\bigrp ≡ u(x)\modulo
{qr}$ is equivalent to $|spose 3w(x)v(x) + |spose 3v(x)w(x)
≡ f(x)\modulo r$, where $u(x) ≡ v(x)w(x) + qf(x) \modulo
{qr}$. We have $\biglp a(x)f(x) + t(x)w(x)\bigrp v(x) + \biglp
b(x)f(x) - t(x)v(x)\bigrp w(x) ≡ f(x) \modulo r$ for all
$t(x)$. Since ??3($v)$ has an inverse modulo $r$, we can find
a quotient $t(x)$ by Algorithm 4.6.1D such that deg($bf - tv)
<$ deg($v)$; for this $t(x)$, deg($af + tw) ≤$ deg($w)$, since
deg($f) ≤$ deg($u) =$ deg($v) +$ deg($w)$. Thus the desired
solution is $|spose 3v(x) = b(x)f(x) - t(x)v(x) = b(x)f(x)$mod
$v(x), |spose 3w(x) = a(x)f(x) + t(x)w(x)$. If \biglp $|spose
ff|spose 3v(x), |spose ff|spose 3w(x)|newtype )$ is another
solution, we have \biglp $|spose 3w(x) - |spose ff|spose 3w(x)\bigrp
v(x) ≡ \biglp |spose ff|spose 3v(x) - |spose 3v(x)\bigrp w(x)
($modulo $r)$. Thus if $r$ is prime, $v(x)$ must divide $|spose
ff|spose 3v(x) - |spose 3v(x)$; but deg($|spose ff|spose 3v
- |spose 3v) <$ deg($v)$, so $|spose ff|spose 3v(x) = |spose
3v(x)$ and $|spose ff|spose 3w(x) = |spose 3w(x)$.

For $p = 2$, the factorization proceeds as follows
(writing only the coefficients, and using bars for negative
digits): Exercise 10 says that $v↓1(x) = (|spose ff1 |spose
ff1 |spose ff1), w↓1(x) = (|spose ff1 |spose ff1 |spose ff1
0 0 |spose ff1 |spose ff1)$ in one-bit two's complement notation.
Euclid's extended algorithm yields $a(x) = (1 0 0 0 0 1), b(x)
= (1 0)$. The factor $v(x) = x↑2 + c↓1x + c↓0$ must have $|c↓1|
≤ \lfloor 1 + \sqrt{113}\rfloor = 11, |c↓0| ≤ 10$, by exercise
20. Three applications of Hensel's lemma yield $v↓4(x) = (1
3 |spose ff1), w↓4(x) = (1 |spose ff3 |spose ff5 |spose ff4
4 |spose ff3 5)$. Thus $c↓1 ≡ 3$ and $c↓0 ≡ -1\modulo {16}$;
the only possible quadratic factor of $u(x)$ is $x↑2 + 3x -
1$. Division fails, so $u(x)$ is irreducible. (Since we have
now proved the irreducibility of this beloved polynomial by
four separate methods, it is unlikely that it has any factors.)

Hans Zassenhaus has observed that we can often
speed up such calculations by increasing $p$ as well as $q:$
In the above notation, we can find $A(x), B(x)$ such that $A(x)V(x)
+ B(x)W(x) ≡ 1 \modulo {pr}$, namely by taking $A(x) = a(x)
+ p|spose 3a(x), B(x) = b(x) + p|spose ffb(x)$, where $|spose
3a(x)V(x) + |spose ffb(x)W(x) ≡ g(x)\modulo r$, $a(x)V(x)
+ b(x)W(x) ≡ 1 - pg(x) \modulo {pr}$. We can also find $C$
with ??3$(V)C ≡ 1\modulo {pr}$. In this way we can lift a
squarefree factorization $u(x) ≡ v(x)w(x) \modulo p$ to its
unique extensions modulo $p↑2, p↑4, p↑8, p↑{16}$, etc. However,
this ``accelerated'' procedure reaches a point of diminishing
returns in practice, as soon as we get to double-precision moduli,
since the time for multiplying multiprecision numbers in practical
ranges outweighs the advantage of squaring the modulus directly.
From a computational standpoint it seems best to work with the
successive moduli $p\hfill p↑2, p↑4, p↑8, \ldotss , p↑E, p↑{E+e},
p↑{E+2e}, p↑{E+3e}, \ldotss $, where $E$ is the smallest power
of 2 with $p↑E$ greater than single precision and $e$ is the
largest integer such that $p↑e$ has single precision.

Hensel's lemma, which he introduced in order to
demonstrate the factorization of polynomials over the field
of $p$-addic numbers (see exercise 4.1--31), can be generalized
in several ways. First, if there are more factors, say $u(x)
≡ v↓1(x)v↓2(x)v↓3(x) \modulo p$, we can find $a↓1(x), a↓2(x),
a↓3(x)$ such that $a↓1(x)v↓2(x)v↓3(x) + a↓2(x)v↓1(x)v↓3(x) +
a↓3(x)v↓1(x)v↓2(x) ≡ 1 \modulo p$, deg($a↓i) <$ deg($v↓i).
($In essence, $1/u(x)$ is expanded in partial fractions as $\sum
a↓i(x)/v↓i(x).)$ An exactly analogous construction now allows
us to lift the factorization without changing the leading coefficients
of $v↓1$ and $v↓2$; we take $|spose 3v↓1(x) = a↓1(x)f(x)$mod
$v↓1(x), |spose 3v↓2(x) = a↓2(x)f(x)$mod $v↓2(x)$, etc. Another
important generalization is to several simultaneous moduli,
of the respective forms $p↑e, (x↓2 - a↓2)↑n|infsup 2, \ldotss
, (x↓t - a↓t)↑n|infsup t$, when performing multivariate gcds
and factorizations. Cf.\ D. Y. Y. Yun, Ph.D. Thesis (M.I.T.,
1974).

\ansno 23. The discriminant of $u(x)$ is a nonzero integer (cf.\
exercise 4.6.1--12), and there are multipoe factors modulo $p$
iff $p$ divides the discriminant. (The factorization of (21)
modulo 3 is $(x + 1)(x↑2 - x - 1)↑2(x↑3 + x↑2 - x + 1)$; squared
factors for this polynomial occur only for $p = 3, 23, 233$
and 121702457. It is not difficult to prove that the smallest
prime that is not unlucky is at most $O(n$ log $Nn)$, if $n
=$ deg($u)$ and $N$ bounds the coefficients of $u(x).)$

%folio 818 galley 4a (C) Addison-Wesley 1978	-
er Programming (Knuth/Addison-Wesley) Answers f. 818 g. 4d
\ansno 24. Multiply a monic polynomial with rational coefficients
by a suitable nonzero integer, to get a primitive polynomial
over the integers. Factor this polynomial over the integers,
and then convert the factors back to monic. (No factorizations
are lost in this way; see exercise 4.6.1--8.)

\ansno 25. Consideration of the constant term shows there are
no factors of degree 1, so if the polynomial is reducible, it
must have one factor of degree 2 and one of degree 3. Modulo
2 the factors are $x(x + 1)↑2(x↑2+x+1)$; this is not much help.
Modulo 3 the factors are $(x + 2)↑2(x↑3+2x+2)$. Modulo 5 they
are $(x↑2 + x + 1)(x↑3 + 4x + 2)$. So we see that the answer
is $(x↑2 + x + 1)(x↑3 - x + 2)$.

\ansno 26. Begin with $D ← (0 \ldotsm 0 1)$, representing the
set \{0\}. Then for 1 ≤ $j ≤ r$, set $D ← D ∨ (D$ shifted left
$d↓j)$, where ∨ denotes logical ``or.'' (Actually we need only
$\lceil(n + 1)/2\rceil$ bits, since $n - j$ is in the set iff
$j$ is.)

\ansno 27. Exercise 4 says that a random polynomial of degree
$n$ is irreducible modulo $p$ with rather low probability, about
$1/n$. But the Chinese remainder theorem implies that a random
monic polynomial of degree $n$ over the integers will be reducible
with respect to each of $k$ distinct primes with probability
about $(1 - 1/n)↑k$, and this approaches zero as $k → ∞$. Hence
almost all polynomials over the integers are irreducible with
respect to infinitely many primes; and almost all primitive
polynomials over the integers are irreducible. [Another proof
has been given by W. S. Brown, {\sl AMM \bf 70} (1963), 965--969.]

\ansno 28. False, we lose all $p↓j$ with $e↓j$ divisible by
$p$. True if $p ≥$ deg($u)$.

\ansno 29. Compute $V↓1(x) =$ gcd\biglp v(x), v↑\prime (x)\bigrp
; this is legitimate since $v↓1(x)$ is relatively prime to $v↑\prime
(x)/v↓1(x)$. Let $v↓0(x) = v(x)/v↓1(x)$, the (squarefree) product
of all irreducible factors of $v(x)$. Compute $d↓1(x) =$ gcd\biglp
u(x), v$↓0(x)\bigrp$ and $u↓1(x) = u(x)/d↓1(x)$. If deg($d↓j)
> 0$ for $j ≥ 1$, compute $|spose ffd↓{j+1}(x) =$ gcd\biglp
$d↓j(x), v↓j(x)\bigrp , d↓{j+1}(x) =$ gcd\biglp $|spose ffd↓{j+1}(x),
u↓j(x)\bigrp , v↓{j+1}(x) = v↓j(x)/|spose ffd↓{j+1}(x), u↓{j+1}(x)
= u↓j(x)/d↓{j+1}(x)$; but if deg($d↓1) = 0$, |newtype terminate
the computation with the answer $d(x) = d↓1(x) \ldotsm d↓j(x).
\biglp$ In this method, $d↓j(x)$ is the squarefree product of
all irreducible factors that occur $≥j$ times in gcd(|newtype
$u(x), v(x))|newtype $. There are several ways to avoid redundant
calculations; for example, the same $p$ can be used in the underlying
gcd computations, and the gcd routine should return the values
of $u(x)/d(x)$ and $v(x)/d(x)$ that it computes. Furthermore
the computation is unsymmetric in $u$ and $v$; it seems better
to interchange the r|spose 7oles of $u$ and $v$ if deg($u) >$
deg($v)$ at the beginning or if deg($u↓j) >$ deg($v↓j)$ when
computing $d↓{j+1}(x).\bigrp$

 \ansno 30. Cf.\ exercise 4; the probability is the coefficient
of $z↑n$ in $(1+a↓{1p}z/p) \times\cr
(1 + a↓{2p}z↑2/p↑2)(1 + a↓{3p}z↑3/p↑3) \ldotsm $, which has the
limiting value $g(z) = (1 + z)(1 + {1\over 2}z↑2) \times\cr
(1 + {1\over 3}z↑3)$. For $1 ≤ n ≤ 10$ the answers are 1, ${1\over
2}$, ${5\over 6}$, ${7\over 12}$, ${37\over 60}$, ${79\over
120}$, ${173\over 280}$, ${101\over 168}$, ${127\over 210, {1033\over
1680}. \biglp$ Let\cr
$f(y) =$ ln($1 + y) - y = O(y↑1)$. Now $g(z) =$ exp\biglp \sum
$↓{n≥1} z↑n/n + \sum ↓{n≥1} f(z↑n/n)\bigrp =\cr
h(z)/(1 - z)$, now it can be shown that the limiting probability
is $h(1) =\cr$
exp\biglp $\sum ↓{n≥1} f(1/n)\bigrp =e↑{-|}≤g \approx .56146$
as $n → ∞$ [cf.\ D. H. Lehmer, {\sl Acta Arith.\ \bf 21} (1972),
379--388]. Indeed, N. G. de Bruijn has established the asymptotic
formula lim$↓{p→∞} a↓{np} =\cr
e↑{-|}≤g + e↑{-|}≤g/n + O(n↑{-2})$.
%folio 819 galley 4b (C) Addison-Wesley 1978	-

|qleft \24skip |newtype {\:r SECTION 4.6.3

\ansno 1. $2↑|≤l↑{(n)}$, the highest
power of 2 less than or equal to $n$.

\ansno 2. Assume that $x$ is input in register
A, and $n$ in location NN; the output is in register X.

|qleft \6skip \qquad \quad {\sl 01\qquad }A1\quad ENTX\quad
1 \qquad 1A{\sl 1}. Initialize.

\quad {\sl 02\qquad \quad \quad }STX \quad Y \qquad
1Y ← 1.

\quad {\sl 03\qquad }\quad \quad STA \quad Z\qquad
1Z ← x.

\quad {\sl 04}\qquad \quad \quad LDA \quad NN\qquad
1N ← n.

\quad {\sl 05}\qquad \quad \quad JMP \quad 2F\qquad
1To A2.
|qleft \qquad \quad ${\sl 06}\qquad 5H\quad SRB 1 \qquad L +
1 - K\qquad$
 |qleft \qquad \quad {\sl 07\qquad }\quad \quad STA \quad N \qquad
L + 1 - K\qquad N → \lfloor N/2\rfloor .
|qleft \qquad \quad {\sl 08}\qquad A5\quad LDA \quad Z \qquad
$LA{\sl 5 }Square Z$.
|qleft \qquad \quad {\sl 09}\qquad \quad \quad MUL \quad Z \qquad
LZ \times Z
|qleft \qquad \quad ${\sl 10}\qquad \quad \quad$ STX \quad Z
\qquad L\quad → Z.
|qleft \qquad \quad {\sl 11}\qquad A2\quad LDA N \qquad LA{\sl
2}. Halve N.
|qleft \qquad \quad {\sl 12\qquad }2H\quad JAE \quad 5B\qquad
L + 1To A5 if $N$ is even.
|qleft \qquad \quad {\sl 13\qquad \quad \quad }SRB \quad 1 \qquad
K
|qleft \qquad \quad {\sl 14\qquad }\quad \quad STA \quad N \qquad
KN → \lfloor N/2\rfloor .
|qleft \qquad \quad {\sl 15}\qquad A3\quad LDA \quad Z \qquad
KA{\sl 3}. Multiply Y by Z.
|qleft \qquad \quad {\sl 16\qquad \quad }\quad MUL \quad Y \qquad
KZ \times Y
|qleft \qquad \quad {\sl 17}\qquad \quad \quad STX \quad Y \qquad
K→ Y.
|qleft \qquad \quad {\sl 18}\qquad A4\quad LDA \quad N \qquad
KA{\sl 4}. N = {\sl 0?
|qleft \qquad \quad 19\qquad }\quad \quad JAP \quad A5\qquad
KIf not, continue at step A5.

|qleft \6skip |newtype \biglp It would be better programming
practice to change the instruction in line 05 to ``JAP'', followed
by an error indication. The running time is $21L + 17K + 13$,
where $L = λ(n)$ is one less than the number of bits in the
binary representation of $n$, and $K = \nu (n)$ is the number
of one bits in $n$'s representation. The running time could
be decreased by $K + 6$ units, by inserting step A4 before step
A3 and adding two new instructions to perform A3 when $N = 0.\bigrp$

For the serial program, we may assume that $n$
is small enough to fit in an index register; otherwise serial
exponentiation is out of the question. The following program
leaves the output in register A:
$$\qquad \qquad \quad S1\quad LD1 \quad N \qquad 1\quad rI1
→ $n$.

\qquad \quad \quad \quad STA \quad X \qquad 1\quad
$X → x$.
|qleft \qquad \qquad \quad \quad \quad JMP \quad 2F\qquad 1\quad
 |qleft \qquad \qquad \quad 1H\quad MUL \quad X \qquad $N - 1\qquad$
rA \times X
|qleft \qquad \qquad \quad \quad \quad SLAX\quad 5\qquad $N
- 1\qquad \qquad →$ rA.
|qleft \qquad \qquad \quad 2H\quad DEC1\quad 1 \qquad ?? $N
\qquad$ rI1 → rI1 - 1.
|qleft \qquad \qquad \quad \quad \quad J1P \quad 1B\qquad $N
\qquad$ Multiply again if rI1 > 0.

|qleft \6skip |newtype The running time for this program is
$14N - 7$; it is faster than the previous program when $n ≥
7$, slower when $n ≥ 8$.

\ansno 3. The sequences of exponents are: (a) 1, 2, 3,
6, 7, 14, 15, 30, 60, 120, 121, 242, 243, 486, 487, 974, 974
[16 multiplications];\xskip (b) 1, 2, 3, 4, 8, 12, 24, 36, 72, 108,
216, 324, 325, 650, 975 [14 multiplications];\xskip (c) 1, 2, 3, 6,
12, 15, 30, 60, 120, 240, 243, 486, 972, 975 [13 multiplications];\xskip
(d) 1, 2, 3, 6, 13, 15, 30, 60, 75, 150, 225, 450, 900, 975
[13 multiplications].\xskip $\biglp$The smallest possible number of multiplications
is 12; this is obtainable by combining the factor method with
the binary method, since 975 =15 \cdot (2$↑6 + 1).\bigrp$

\ansno 4. $(777777)↓8 = 2↑{18} - 1$.

|qleft \3skip |hangindent3 {\bf 5. T1.} [Initialize.] Set LINKU[$j]$
→ 0 for $1 ≤ j ≤ 2↑r$, and set $k → 0$, LINKR[0] → 1, LINKR[1]
→ 0.

\ansalgstep? T2.} Change level.] (Now level $k$
of the tree has been linked together from left to right, starting
at LINKR[0].) If $k = r$, the algorithm terminates. Otherwise
set $n →$ LINKR[0], $m → 0$.

|qleft \3skip \qquad {\bf T3.} [Prepare for {\sl n.] (}Now $n$
is a node on level $k$, and $m$ points to the rightmost node
currently on level $k + 1.)$ Set $q ← 0, s ← n$.

|qleft \3skip \qquad {\bf T4.} [Already in tree?] (Now $s$ is
a node in the path from the root to $n.)$ If LINKU[$n + s]$
≠ 0, go to T6 (the value $n + s$ is already in the tree).

|qleft \3skip \qquad {\bf T5.} [Insert below {\sl n.]} If $q
= 0$, set $m↑\prime ← n + s$. Set LINKR[$n + s] ← q$, LINKU[$n
+ s] ← n, q ← n + s$.

|qleft \3skip \qquad {\bf T6.} [Move up.] Set $s ←$ LINKU[{\sl
s].} If $s ≠ 0$, return to T4.

|qleft \3skip \qquad {\bf T7.} [Attach group.] If $q ≠ 0$, set
LINKR[$m] ← q, m ← m↑\prime $.

|qleft \3skip \qquad {\bf T8.} [Move {\sl n.]} Set $n ←$ LINKR[{\sl
n].} If $n ≠ 0$, return to T3.

|qleft \3skip \qquad {\bf T9.} [End of level.] Set LINKR[$m]
← 0, k ← k + 1$, and return to T2.

\ansno 6. Prove by induction that
the path to the number $2↑e|infsup 0 + 2↑e|infsup 1 + \cdots
+ 2↑e|infsup t$, if $e↓0 > e↓1 > \cdots >e↓t ≥ 0$, is $1, 2,
2↑2, \ldotss , 2↑e|infsup 0, 2↑e|infsup 0 + 2↑e|infsup 1, \ldotss
, 2↑e|infinf 0 + 2↑e|infsup 1 + \cdots + 2↑e|infsup t$; furthermore,
the sequence of exponents on each level are in decreasing lexicographic
order.

\ansno 7.} The binary and factor methods require
one more step to compute $x↑{2n}$ than $x↑n$; the power tree
method requires at most one more step. Hence (a) 15 \cdot 2$↑k;\xskip
(b) $33 \cdot 2↑k$;\xskip (c) $23 \cdot 2↑k$;\xskip $k = 0$, 1, 2, 3,
$\ldotss\,$.

\ansno 8. The power tree always includes the node
$2m$ at one level below $m$, unless it occurs at the same level
or an earlier level; and it always includes the node $2m + 1$
at one level below $2m$, unless it occurs at the same level.
(Computational experiments have shown that $2m$ is below $m$
for all $m ≤$ 2000, but it appears very difficult to prove this
in general.)

\ansno 10. By using the ``FATHER'' representation discussed
in Section 2.3.3: Make use of a table {\sl f[j], 1 ≤ J ≤ 100},
such that $f[1] = 0$ and {\sl f[j]} is the number of the node
just above $j$ for $j ≥ 2$.\xskip (The fact that each node of this
tree has degree at most two has no effect on the efficiency
of this representation; it just makes the tree look prettier
as an illustration.)

\ansno 11. 1, 2, 3, 5, 10, 20, (23 or 40), 43; 1, 2, 4, 8, 9,
17, (26 or 34), 43; 1, 2, 4, 8, 9, 17, 34, (43 or 68), 77; 1,
2, 4, 5, 9, 18, 36, (41 or 72), 77. If either of the latter
two paths were in the tree we would have no possibility for
$n = 43$, since the tree must contain either 1, 2, 3, 5 or 1,
2, 4, 8, 9.

\ansno 12. No such infinite tree can exist since $l(n) ≠ l??(n)$
for some $n$.
|qleft β????????????|newtype W58320---Computer Pro
%folio 821 galley 5 (C) Addison-Wesley 1978	-
gramming\quad (Knuth/Addison-Wesley)\quad Answers\quad f. 821\quad
g. 5d
\ansno 13. For Case 1, use a Type-1 chain followed by $2↑{A+C}
+ 2↑{B+C} + 2↑A + 2↑B$; or use the factor method. For Case 2,
use a Type-2 chain followed by 2$↑{A+C+1} + 2↑{B+C} + 2↑A +
2↑B$. For Case 3, use a Type-5 chain followed by addition of
$2↑A + 2↑{A-1}$, or use the factor method. For Case 4, $n =
135 \cdot 2↑D$, so we may use the factor method.

\ansno 14. (a) It is easy to verify that steps $r - 1$ and $r
- 2$ are not both small, so let us assume that step $r - 1$
is small and step $r - 2$ is not. If $c = 1$, then $λ(a↓{r-1})
= λ(a↓{r-k})$, so $k = 2$; and since $4 ≤ \nu (a↓r) = \nu (a↓{r-1})
+ \nu (a↓{r-k}) - 1 ≤ \nu (a↓{r-1}) + 1$, we have $\nu (a↓{r-1})
≥ 3$, making $r - 1$ a star step (lest $a↓0, a↓1, \ldotss , a↓{r-3},
a↓{r-1}$ include only one small step). Then $a↓{r-1} = a↓{r-2}
+ a↓{r-q}$ for some $q$, and if we replace $a↓{r-2}, a↓{r-1},
a↓r$ by $a↓{r-2}, 2a↓{r-2}, 2a↓{r-2} + a↓{r-q} = a↓r$, we obtain
another counterexample chain in which step $r$ is small; but
this is impossible. On the other hand, if $c ≥ 2$, then 4 ≤
$\nu (a↓r) ≤ \nu (a↓{r-1}) + \nu (a↓{r-k}) - 2 ≤ \nu (a↓{r-1})$;
hence $\nu (a↓{r-1}) = 4, \nu (a↓{r-k}) = 2$, and $c = 2$. This
leads readily to an impossible situation by a consideration
of the six types in the proof of Theorem B.

(b) If $λ(a↓{r-k}) < m - 1$, we have $C ≥ 3$, so
$\nu (a↓{r-k}) + \nu (a↓{r-1}) ≥ 7$ by (22); therefore both
$\nu (a↓{r-k})$ and $\nu (a↓{r-1})$ are ≥3. All small steps
must be $≤r - k$, and $λ(a↓{r-k}) = m - k + 1$. If $k ≥ 4$,
we must have $c = 4, k = 4, \nu (a↓{r-1}) = \nu (a↓{r-4}) =
4$; thus $a↓{r-1} ≥ 2↑m + 2↑{m-1} + 2↑{m-2}$, and $a↓{r-1}$
must equal $2↑m + 1↑{m-1} + 2↑{m-2} + 2↑{m-3}$; but $a↓{r-4}
≥ {1\over 8}a↓{r-1}$ now implies that $a↓{r-1} = 8a↓{r-4}$.
Thus $k = 3$ and $a↓{r-1} > 2↑m + 2↑{m-1}$. Since $a↓{r-2} <
2↑m$ and $a↑{r-3} < 2↑{m-1}$, step $r - 1$ must be a doubling;
but step $r - 2$ is a nondoubling, since $a↓{r-1} ≠ 4a↓{r-3}$.
Furthermore, since $\nu (a↓{r-3}) ≥ 3, r - 3$ is a star step;
and $a↓{r-2} = a↓{r-3} + a↓{r-5}$ would imply that $a↓{r-5}
= 2↑{m-2}$, hence we must have $a↓{r-2} = a↓{r-3} + a↓{r-4}$.
As in a similar case treated in the text, the only possibility
is now seen to be $a↓{r-4} = 2↑{m-2} + 2↑{m-3}, a↓{r-3} = 2↑{m-2}
+ 2↑{m-3} + 2↑{d+1} + 2↑d, a↓{r-1} = 2↑m + 2↑{m-1} + 2↑{d+2}
+ 2↑{d+1}$, and even this possibility is impossible.

\ansno 16. ??3$↑B(n) = λ(n) + \nu (n) - 1$; so if $n = 2↑k,
??3↑B(n)/λ(n) = 1$, but if $n = 2↑{k+1} - 1, ??3↑B(n)/λ(n) =
2$.

\ansno 17. Let $i↓1 < \cdots < i↓t$. Delete any intervals $I↓k$
that can be removed without affecting the union $I↓1 ∪ \cdots
∪ I↓t$.\xskip (The interval $(j↓k, i↓k]$ may be dropped out if either
$j↓{k+1} ≤ j↓k$ or $j↓1 < j↓k$ or $j↓1 < j↓2 < \cdots$ and $j↓{k+1}
≤ i↓{k-1}.)$ Now combine overlapping intervals $(j↓1, i↓1],
\ldotss , (j↓d, i↓d]$ into an interval $(j↑\prime , i↑\prime
] = (j↓1, i↓d]$ and note that
$$\3skip $a↓{i↑}(1 + \delta )↑i|infsup 1|supsup -|supsup j|infsup
1↑{+\\\+i}|infsup d↑{-j}|infsup d ≤ a↓{j↑}(1 + \delta )↑{2(i↑-j↑})$,
|qctr \9skip since each point of $(j↑\prime , i↑\prime ]$ is
covered at most twice in $(j↓i, i↓1] ∪ \cdots ∪ (j↓d, i↓d]$.

\ansno 18. Call $f(m)$ a ``nice'' function|spose $↑m\sqrt{f(m)}
→ 1$ as $m → ∞$, that is, \biglp log $f(m)\bigrp /m → 0$. A
polynomial in $m$ is nice. The product of nice functions is
nice. If $g(m) → 0$ and $c$ is a positive constant, then $c↑{mg(m)}$
is nice; also $({2m\atop mg(m)}$ is nice, for by Stirling's
approximation this is equivalent to saying that $g(m)$ log\biglp
$1/g(m)\bigrp → 0$.

|qleft \3skip \qquad Now replace each term of the summation
by the maximum term that is attained for any $s, t, v$. The
total number of terms is nice, and so are $({m+s\atop t+v}),
({t+v\atop v}) ≤ 2↑{t+v}$, and $β↑2|infsup v$, because $(t +
v)/m → 0$. Finally, $({(m+s)|supsup 2\atop t}) ≤ (2m)↑{2t}/t!
< (4m↑2/t)↑te↑t$, where $(4e)↑t$ is nice; setting $t$ to its
maximum value (1 - ${1\over 2}ε)m/λ(m)$, we have $(m↑2/t)↑t
= (|newtype (mλ(m)/(1 - {1\over 2}ε)\bigrp ↑t = 2↑{m(1-|}≤e↑{/2)}
\cdot f(m)$, where $f(m)$ is nice. Hence the entire sum is less
than $α↑m$ for large $m$, if $α = 2↑{1-|}≤h, 0 < \eta < {1\over
2}ε$.

\ansno 19. (a) $M ∩ N, M ∪ N, M |spose |infsup +∪ N$, respectively;
see Eqs.\ 4.5.2--6, 4.5.2--7.

(b) $f(z)g(z)$, lcm\biglp $f(z), g(z)\bigrp $,
gcd\biglp $f(z), g(z)\bigrp $.\xskip (For the same reasons as (a),
because the monic irreducible polynomials over the complex numbers
are precisely the polynomials $z - \zeta .)$

(c) Commutative laws $A ?? B = B ?? A, A ∪ B =
B ∪ A, A ∩ B = B ∩ A$. Associative laws $A ?? (B ?? C) = (A
?? B) ?? C, A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B)
∩ C$. Distributive laws $A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), A
∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ?? (B ∪ C) = (A ?? B) ∪ (A
?? C), A ?? (B ∩ C) = (A ?? B) ∩ (A ?? C)$. Idempotent laws
$A ∪ A = A, a = A$. Absorption laws $A ∪ (A ∩ B) = A, A ∩ (A
∪ B) = A, A ∩ (A ?? B) = A, A ∪ (A ?? B) = A ?? B$. Identity
and zero laws $ ?? A = A, ∪ A = A, ∩ A = $, where is the empty
multiset. Counting law $A ?? B = (A ∪ B) ?? (A ∩ B)$. Further
properties analogous to those of sets come from the partial
ordering defined by the rule $A \subset B$ iff $A ∩ B = A$ (iff
$A ∪ B = B)$.

{\sl Notes: }Other common applications of multisets
are zeros and poles of meromorphic functions, invariants of
matrices in canonical form, invariants of finite Abelian groups,
etc.; multisets can be useful in combinatorial counting arguments
and in the development of measure theory. The terminal strings
of a noncircular context-Free grammar form a multiset that
is a set if and only if the grammar is unambigous. Although
multisets appear frequently in mathematics, they often must
be treated rather clumsily because there is currently no standard
way to treat sets with repeated elements. Several mathemaicians
have voiced their belief that the lack of adequate terminology
and notation for this common concept has been a definite handicap
to the development of mathematics. (A multiset is, of course,
formally equivalent to a mapping from a set into the nonnegative
integers, but this formal equivalence is of little or no practical
value for creative mathematical reasoning.) The author has discussed
this matter with many people in an attempt to find a good remedy.
some of the names suggested for the concept were list, bunch,
heap, sample, weighted set, collection; but these words either
conflict with present terminology, have an improper connotation,
or are too much of a mouthful to say and to write conveniently.
It does not seem out of place to coin a new word for such an
important concept, and ``multiset'' has been suggested by N.
G. de Bruijn. The notation ``$A ?? B$'' has been selected by
the author to avoid conflict with existing notations and to
stress the analogy with set union. It would not be as desirable
to use ``$A + B$'' for this purpose, since algebraists have
found that $A + B$ is a good notation for \{$α + β | α \in A$
and $β \in B\}$. If $A$ is a multiset of nonnegative integers,
let $G(z) = \sum ↓{n\A} z↑n$ be a generating function corresponding
to $A$.\xskip (Generating functions with nonnegative integer coefficients
obviously correspond one-to-one with multisets of nonnegative
integers.) If $G(z)$ corresponds to $A$ and $H(z)$ to $B$, then
$G(z) + H(z)$ corresponds to $A ?? B$ and $G(z)H(z)$ corresponds
to $A + B$. If we form ``Drichlet'' generating functions $g(z)
= \sum ↓{n\A} 1/n↑z, h(z) = \sum ↓{n\B} 1/n↑z$, the product
$g(z)h(z)$ corresponds to the multiset product $AB$.

\ansno 20. Type 3: $(S↓0, \ldotss , S↓r) = (M↓{00}, \ldotss ,
M↓{r0}) = (\{0\}, \ldotss , \{A\}, \{A - 1, A\{, \{A - 1, A,
A\}, \{A - 1, A - 1, A, A, A\}, \ldotss , \{A + C - 3, A + C
- 2, A + C - 2, A + C - 2\})$. Type 5: $(M↓{00}, \ldotss , M↓{r0})
= (\{0\}, \ldotss , \{A\}, \{A - 1, A\}, \ldotss , \{A + C - 1,
A + C\}, \{a + C - 1, A + C - 1, A + C\}, \ldotss , \{A + C +
D - 1, A + C + D - 1, A + C + D\}), (M↓{01}, \ldotss , M↓{r1})
= ( , \ldotss , , , \ldotss , , \{A + C - 2\}, \ldotss , \{A +
c + D - 2\}), S↓i = M↓{i0} ?? M↓{i1}$.

\ansno 21. For example, let $u = 2↑{8q+5}, x = (2↑{(q+1)u} -
1)/(2↑u - 1) = 2↑{qu} + \cdots + 2↑u + 1, y = 2↑{(q+1)u} + 1$.
Then $xy = (2↑{2(q+1)u} - 1)/(2↑u - 1)$; if $n = 2↑{4(q+1)u}
+ xy$, we have ??3$(n) ≤ 4(q + 1)u + q + 2$ by Theorem F\null, but
$??3??(n) = 4(q + 1)u + 2q + 2$ by Theorem H.

\ansno 22. Underline everything except the $u - 1$ insertions
used in the calculation of $x$.

\ansno 23. Theorem G (everything underlined).

\ansno 24. Use the numbers $(B↑a|infsup i - 1)/(B - 1), 0 ≤
i ≤ r$, underlined when $a↓i$ is underlined; and $c↓kB↑{i-1}(B↑b|infsup
j - 1)/(B - 1)$ for $0 ≤ j < t, 0 < i ≤ k ≤ ??3↑0(B)$, underlined
when $c↓k$ is underlined, where $c↓0, c↓1, . . $. is a minimum
length ??3$↑0-chain for B$. To prove the second inequality,
let $B = 2↑m$ and use (3). (The second inequapty, is rarely,
if ever, an improvement on Theorem G.)
|qleft u????????????|newtype W58320---Co
%folio 824 galley 6a (C) Addison-Wesley 1978	-
mputer Programming\quad (Knuth/Addison-Wesley)\quad Answers\quad
f. 824\quad g. 6d
\ansno 25. We may assume that $d↓k = 1$. Use the rule $R A↓{k-1}
\ldotsm A↓1$, where $A↓j = ``XR$'' if $d↓j = 1, A↓j =$ ``R''
otherwise, and where ``R'' means take the square root, ``X''
means multiply by $x$. For example, if $y = (.1101101)↓2$, the
rule is R R XR XR R XR XR. (There exist binary square-root extraction
algorithms suitable for computer hardware, requiring an execution
time comparable to that of division; computers with such hardware
could also calculate more general fractional powers with the
technique in this exercise.)

\ansno 26. If we know the pair $(F↓k, F↓{k-1})$, then $(F↓{k+1},
F↓k) = (F↓k + F↓{k-1}, F↓k)$ and $(F↓{2k}, F↓{2k-1}) = (F↑{2}↓{k}
+ 2F↓kF↓{k-1}, F↑{2}↓{k} + F↑{2}↓{k-1})$; so a binary method
can be used to calculate $(F↓n, F↓{n-1})$, using $O($log $n)$
arithmetic operations. Perhaps better is to use the pair of
values $(F↓k, L↓k)$, where $L↓k = F↓{k-1} + F↓{k+1}$ (cf.\ Section
4.5.4); then $(F↓{k+1}, L↓{k+1}) = \biglp {1\over 2}(F↓k + L↓k),
{1\over 2}(5F↓k + L↓k)\bigrp , (F↓{2k}, L↓{2k}) = (F↓kL↓k, L↑{2}↓{k}
- 2(-1)↑k\bigrp $.

For the general linear recurrence $x↓n = a↓1x↓{n-1}
+ \cdots + a↓dx↓{n-d}$, we can compute $x↓n$ in $O(d↑3$ log
$n)$ arithmetic operations by computing the $n$th power of an
appropriate $d d$ matrix. (This observation is due to J. C.
P. Miller and D. J. S. Brown, {\sl Comp.\ J.} {\bf 9} (1966),
188--190.)

\ansno 27. First form the $2↑m - m - 1$ products $x↑{e↓1}↓{1}
\ldotss x↑{e↓m}↓{m}$, where $0 ≤ e↓j ≤ 1$ and $e↓1 + \cdots +
e↓m ≥ 2$. Then if $n↓j = (d↓{j|}≤l \ldotsm d↓{j1}d↓{j0})↓2$,
the sequence begins with $x↑{d↓1λ}↓{1} \ldotsm x↑{d↓{m|}≤l}↓{m}$
and then we square, and multiply by $x↑{d↓{1i}}↓{1} \ldotss x↑{d↓{mi}}↓{m}$,
for $i = λ - 1, \ldotss , 1, 0. \biglp$ Straus [{\sl AMM \bf 71}
(1964), 807--808] has shown that $2λ(n)$ may be replaced by
(1 + $ε)λ(n)$ for any $ε > 0$, by generalizing this binary method
to $2↑k$-ary as in Theorem D\null. At least ??3$(n↓1 + \cdots + n↓m)$
multiplications are obviously required.\bigrp

\ansno 28. (a) $x y = x ∨ y ∨ (x + y)$, where
``∨'' is logical ``or'', cf.\ exercise 4.6.2--26; clearly $\nu
(x y) ≤ \nu (x ∨ y) + \nu (x ∧ y) = \nu (x) + \nu (y)$.\xskip (b)
Note first that $A↓{i-1}/2↑d|infsup i|infsup -|infsup 1 \subset
A↓i/d↑i$ for $1 ≤ r$. Secondly, note that $d↓j = d↓{i-1}$ in
a nondoubling; for otherwise $a↓{i-1} ≥ 2a ≥ a↓j + a↓k = a↓i$.
Hence $A↓j \subset A↓{i-1}$ and $A↓k \subset A↓{i-1}/2↑d|infsup
j↑{-d}|infsup k$.\xskip (c) An easy induction on $i$, except that
close steps need closer attention. Let us say that $m$ has property
$P(α)$ if the 1's in its binary representation all appear in
consecutive blocks of $≥α$ in a row. If $m$ and $m↑\prime$ have
$P(α)$, so does $m m↑\prime $; if $m$ has $P(α)$ then $\rho
(m)$ has $P(α + \delta )$. Hence $B↓i$ has $P(1 + \delta c↓i)$.
Finally if $m$ has $P(α)$ then $\nu \biglp \rho (m)) ≤ (α +
\delta )\nu (m)/α$; for $\nu (m) = \nu ↓1 + \cdots + \nu ↓q$,
where each block size $\nu ↓j$ is $≥α$, hence $\nu \biglp \rho
(m)\bigrp ≤ (\nu ↓1 + \delta ) + \cdots + (\nu ↓q + 8) ≤ (1
+ \delta /α)\nu ↓1 + \cdots + (1 + \delta /α)\nu ↓q$. (d) Let
$f = b↓r + c↓r$ be the number of nondoublings and $s$ the number
of small steps. If $f ≥ 3.271$ lg $\nu (n)$ we have $s ≥$ lg
$\nu (n)$ as desired, by (16). Otherwise we have $a↓i ≤ (1 +
2↑{-|}≤d)↑b|infsup i2↑c|infsup i↑{+d}|infsup i$ for $0 ≤ i ≤
r$, hence $n ≤ \biglp (1 + 2↑{-|}≤d)/2\bigrp ↑b|infsup r2↑r$,
and $r ≥$ lg $n + b↓r - b↓r$ lg(1 + 2$↑{-|}≤d) ≥$ lg $n +$ lg
$\nu (n) $- lg($1 + \delta c↓r) - b↓r$ lg(1 + 2$↑{-|}≤d)$. Let
$\delta = \lceil$ lg($f + 1)\rceil $; then ln($1 + 2↑{-|}≤d)
≤$ ln\biglp 1 + 1/($f + 1)\bigrp ≤ 1/(f + 1) ≤ \delta /(1 +
\delta f)$, and it follows that lg(1 + $\delta x) + (f - x)$lg(1
+ $2↑{-|}≤d) ≤$ lg($1 + \delta f)$ for $0 ≤ x ≤ f$. Hence finally
$??3(n) ≥$ lg $n +$ lg $\nu (n) $- lg\biglp 1 + (3.271 lg $\nu
(n)\bigrp \lceil$ lg\biglp $1 + 3.271$ lg $\nu (n)|newtype )|newtype
)\rceil )|newtype . [{\sl Theoretical Comp.\ Sci.\ \bf 1} (1975),
1--12.]

\ansno 29. In the paper just cited, Sch|spose 4onhage
has refined the method of exercise 28 to prove that $??3(n)
≥$ lg $n +$ lg $\nu (n) - 2.13$ for all $n$. Can the remaining
gap be closed?

\ansno 30. $n = 31$ is the smallest example;
$??3(31) = 7$, but 1, 2, 4, 8, 16, 32, 31 is an addition-subtraction
chain of length 6. Erd|spose 4os has stated that Theorem E holds
also for addition-subtraction chains. Sch|spose 4onhage has
extended his lower bound of exercise 28 to addition-subtraction
chains, with $\nu (n)$ replaced by $|spose 3\nu (n) =$ minimum
number of nonzero digits to represent $n = (n↓q \ldotsm n↓0)↓2$
where each $n↓j$ is -1, 0, or +1; $|spose 3\nu (n)$ is the number
of 1's, in the ordinary binary representation of $n$, that
are immediately preceded by 0 or by the string 00(10)$↑k1$ for
some $k ≥ 0.)$

\ansno 32. Andrew C. Yao has essentially found the asymptotic
behavior for fixed $m$, by generalizing the 2$↑k$-ary method
to obtain the upper bound $λ(n↓m) + O\biglp \sum ↓{1≤i≤m} λ(n↓i)/λλ(n↓i)\bigrp
$.

%folio 826 galley 6b (C) Addison-Wesley 1978	-
|qleft \24skip |newtype {\:r SECTION 4.6.4

\ansno 1. Set $y ← x↑2$, then compute
\biglp (\ldotsm(u↓{2n+1}y + u↓{2n-1})y + u↓1\bigrp x$.

\ansno 2. Replacing $x$ in (2) by the polynomial $x + x↓0$ leads
to the following procedure:
$$|indent \qquad {\bf G1.} Do step G2, for $k = n, n - 1, \ldotss
, 0$ (in this order), and stop.

|qleft \3skip \qquad {\bf G2.} Set $v↓k ← u↓k$, and then set
$v↓j ← v↓j + x↓0v↓{j+1}$ for $j = k, k + 1, \ldotss , n - 1.
($When $k = n$, this step simply sets $v↓n ← u↓n.)$

|qleft \3skip |cancelindent The computations turn out to be
identical to those in H1, H2, but performed in a different order.

\ansno 3. The coefficient of $x↑k$ is a polynomial in $y$ that
may be evaluated by Horner's rule: $\biglp \ldotsm(u↓{n,0}x
+ (u↓{n-1,1}y + u↓{n-1,0}))x + \cdotss\bigrp x + \biglp (\ldotsm
(u↓{0,n}y + u↓{0,n-1})y + \cdotss)y + u↓{0,0}\bigrp $.\xskip (For
a ``homogeneous'' polynomial, such as $u↓nx↑n + u↓{n-1}x↑{n-1}y
+ \cdots + u↓1xy↑{n-1} + u↓0y↑n$, another scheme is more efficient:
first divide $x$ by $y$, evaluate a polynomial in $x/y$, then
multiply by $y↑n.\bigrp$

 \ansno 4. Rule (2) involves $4n$ or $3n$ real multiplications
and $4n$ or $7n$ real additions; (3) is worse, it takes 4$n
+ 2$ or $4n + 1$ mults, $4n + 2$ or $4n + 5$ odds.

\ansno 5. One multiplication to compute $x↑2; \lfloor
n/2\rfloor$ multiplications and \lfloor $n/2\rfloor$ additions
to evaluate the first line; \lceil $n/2\rceil$ multiplications
and $\lceil n/2\rceil - 1$ additions to evaluate the second
line; and one addition to add the two lines together. Total:
$n + 1$ multiplications and $n$ additions.

\ansno 6. {\bf J1.} Compute and store the values $x↑{2}↓{0},
\ldotss , x↑{j-\lfloor n/2\rfloor }↓{0}$.

|qleft \3skip \qquad {\bf J2.} Set $v↓j ← u↓jx↑{j-\lfloor n/2\rfloor
}↓{0}$ for $0 ≤ j ≤ n$.

|qleft \3skip \qquad {\bf J3.} For $k = 0, 1, \ldotss , n - 1$,
set $v↓j ← v↓j + v↓{j+1}$ for $j = n - 1, \ldotss , k + 1, k$.

|qleft \3skip \qquad {\bf J4.} Set $v↓j ← v↓jx↑{\lfloor n/2\rfloor
-j}↓{0}$ for $0 ≤ j ≤ n$.

|qleft \3skip There are $(n + n↑2)/2$ additions, $n + \lceil
n/2\rceil - 1$ multiplications, $n$ divisions. Another multiplication
and division can be saved by treating $v↓n$ and $v↓0$ as special
cases. {\sl Reference{\sl :} SIGACT News \bf 7}, 3 (Summer 1975),
32--34.

\ansno 7. Let $x↓j = x↓0 + jh$, and consider (42), (44). Set
$y↓j ← u(x↓j)$ for $0 ≤ j ≤ n$. For $k = 1, 2, \ldotss , n$ (in
this order), set $y↓j ← y↓j - y↓{j-1}$ for $j = k, k + 1, \ldotss
, n$ (in this order). Now $β↓j = y↓j$ for all $j$.

\ansno 8. See (43).

\ansno 9. [{\sl Combinatorial Mathematics (}Buffalo: Math. Ass'n
of America, 1963), 26--28.] This formula can be regarded as
an application of the principle of inclusion and exclusion (Section
1.3.3), since the sum of the terms for $n - ε↓1 - \cdots - ε↓n
= k$ is the sum of all $x↓{1j}|infinf 1x↓{2j}|infinf 2 \ldotsm
x↓{nj}|infinf n$ for which $k$ values of the $j$, do not appea.
A direct proof can be given by observing that the coefficient
of $x↓{1j}|infinf 1 \ldotss x↓{nj}|infinf n$ is
$$$\sum (-1)↑{n-|}≤e|infsup 1↑{-\\\-|}≤e|infsup nε↓j|infinf
1 \ldotss ε↓j|infinf n$;
|qctr \9skip if the $j$'s are distinct, this equals unity, but
if $j↓1, \ldotss , j↓n ≠ k$ then it is zero, since the terms
for $ε↓k = 0$ cancel the terms for $ε↓k = 1$.

To evaluate the sum efficiently, we can start
with $ε↓1 = 1, ε↓2 = \cdots = ε↓n = 0$, and we can then proceed
through all combinations of the $??$'s in such a way that only
one $ε$ changes from one term to the ne t. (See ``Gray code''
in Chapter 7.) The work to compute the first term is $n - 1$
multiplications; the subsequent 2$↑|εn - 2$ terms each involve
$n$ additions, then $n - 1$ multiplications, then one more addition.
Total: $(2↑n - 1)(n - 1)$ multiplications, and $(2↑n - 2)(n
+ 1)$ additions. Only $n + 1$ temp storage locations are needed,
one for the main partial sum and one for each factor of the
cur|newtype W58320
%folio 828 galley 7 (C) Addison-Wesley 1978	-
---Computer Programming\quad (Knuth/Addison-Wesley)\quad Answers\quad
f. 828\quad g. 7d
\ansno 10. $\sum ↓{1≤k<n} (k + 1)({n\atop k+1}) = n(2↑{n-1}
- 1)$ multiplications and $\sum ↓{1≤k<n} k({n\atop k+1}) =\cr
n2↑{n-1} - 2↑n + 1$ additions. This is approximately half as
many arithmetic operations as the method of exercise 9, although
it requires a more complicated program to control the sequence.
Approximately $({n\atop \lceil n/2\rceil }) + ({n\atop \lceil
n/2\rceil -1})$ temporary storage locations must be used, and
this grows exponentially large (on the order of 2$↑n/\sqrt{n}4↑n/n↑{1.5}$.

The method in this exercise is equivalent to the
unusual matrix factorization of the permanent function, given
by Jurkat and Ryser in {\sl J. Algebra \bf 5} (1967), 342--357.
It may also be regarded as an application of (39), (40), in
an appropriate sense.

\ansno 12. (J. Hopcroft and L. R. Kerr have shown among other
things that 7 multiplications are necessary in 2 \times 2 matrix
multiplication [{\sl SIAM J. Appl.\ Math.\ \bf 20} (1971), 30--36].
R. L. Probert has shown that all 7-multiplication schemes, in
which each multiplication takes a linear combination of elements
from one matrix and multiplies by a linear combination of elements
from the other, must have at least 15 additions [{\sl SIAM J.
Computing}, to appear]. The best lower bound now known for large
$n$ is $2n↑2 - n$ multiplications, a result due to D. Kirkpatrick.
For $n = 3$, J. D. Laderman [{\sl Bull.\ Amer.\ Math.\ Soc.\ \bf 82}
(1976), 126--128] has shown that 23 noncommutative multiplications
suffice.)

\ansno 13. $F(t↓1, \ldotss , t↓n) = \biglp \sum ↓{0≤s↓1<m↓1,...,0≤s↓n<m↓n}$
exp\biglp $-2πi(s↓1t↓1/m↓1 + \cdots + s↓nt↓n/m↓n)f(s↓1, \ldotss
, s↓n)\bigrp /m↓1, \ldotss m↓n$, by summing geometric series.
The inverse transform times $m↓1 \ldotsm m↓n$ can be found by
doing a regular transform and interchanging $t↓j$ with $m↓j
- t↓j$ when $t↓j ≠ 0$, cf.\ exercise 4.3.3--15.

|newtype (If we regard $F(t↓1, \ldotss , t↓n)$
as the coefficient of $x↑{t↓1}↓{1} \ldotss x↑{t↓n}↓{n}$ in a
multivariate polynomial, the finite Fourier transform amounts
to evaluation of this polynomial at roots of unity, and the
inverse transform amounts to finding the interpolating polynomial.|newtype
)

\ansno 14. (a) Let $m = 2, F(t↓1, t↓2, \ldotss , t↓n) = F(2↑{n-1}t↓n
+ \cdots + 2t↓2 + t↓1), f(s↓1, s↓2, \ldotss , s↓n) = f(2↑{n-1}s↓1
+ 2↑{n-2}s↓2 + \cdots + s↓n)$; note the reversed treatment between
$t$'s and $s$'s. Also let $g↓k(s↓k, \ldotss , s↓n, t↓k)$ be $\omega$
raised to the 2$↑{k-1}t↓k(s↓n + 2s↓{n-1} + \cdots + 2↑{n-k}s↓k)$
power. It is possible to gain some speed by combining steps
$k$ and $k + 1$, for $k = 1, 3, . . .$; this expedites several
of the computations of sines and cosines. [The fast Fourier
transform algorithm is essentially due to C. Runge and H. K|spose
4onig in 1924, and it was generalized by J. W. Cooley and J.
W. Tukey, {\sl Math.\ Comp.\ \bf 19} (1965), 297--301. Its interesting
history has been traced by J. W. Cooley, P. A. W. Lewis, P.
D. Welch, {\sl Proc.\ IEEE} {\bf 55} (1967), 1675--1677. Details
concerning its use have been discussed by R. C. Singleton, {\sl CACM
\bf 10} (1967), 647--654; M. C. Pease, {\sl JACM \bf 15} (1968),
252--264; G. D. Berglund, {\sl Math.\ Comp.\ \bf 22} (1968), 275--279,
{\sl CACM \bf 11} (1968), 703--710.]

[(b)???]→→→→→ (a) Let $N$ be the smallest power of 2 that exceeds
$2n$, and let $u↓{n+1} = \cdots = u↓{N-1} = v↓{n+1} = \cdots
= v↓{N-1} = 0$. If $U↓s = \sum ↓{0≤t<N} u↓t\omega ↑{st}, V↓s
= \sum ↓{0≤t<N} v↓t\omega ↑{st}, 0 ≤ s < N, \omega = e↑{2|}≤p↑{i/N}$,
then $\sum ↓{0≤s<N} U↓sV↓s\omega ↑{-st} = N \sum u↓t|infinf
1v↓t|infinf 2$. The latter sum is taken over all $t↓1$ and $t↓2$
with $0 ≤ t↓1, t↓2 < N, t↓1 + t↓2 ≡ t\modulo N$. The terms
vanish unless $t↓1 ≤ n, t↓2 ≤ n$, so $t↓1 + t↓2 < N$; thus the
sum is the coefficient of $z↑t$ in the product $u(z)v(z)$. If
we use the method of (a) to compute the Fourier transforms and
the inverse transforms, the number of complex operations is
$O(N$ log $N) + O(N$ log $N) + O(N) + O(N$ log $N)$; and $N
< 4n. [$Cf.\ Section 4.3.3 and the paper by J. M. Pollard, {\sl Math.\
Comp.\ \bf 25} (1971), 365--374.]
|qleft |newtype \qquad The number $\omega$ cannot be represented
exactly inside a computer, but V. Strassen has shown that it
isn't necessary to have too much accuracy to deduce exact results
when the coefficients are integers [{\sl Computing} {\bf 7}
(1971), 281--292].

It is possible to use an {\sl integer} number
$\omega$ that is of order $2↑t$ modulo a prime $p$, and to
determine the results modulo sufficiently many primes. Useful
primes in this regard, together with their least primitive roots
$r$ (from which we take $\omega = r↑{(p-1)/2}|supsup t$ mod
$p$ when $p$ mod $2↑t = 1)$, can be found as described in Section
4.5.4. For $t = 9$, the largest cases W2$↑{35}$ are $p = 2↑{35}
- 512a + 1$, where $(a, r) = (28, 7), (31, 10), 34, 13), (56,
3), (58, 10), (76, 5), (80, 3), (85, 11), 91, 5), (101, 3)$;
the ten largest cases <2$↑{31} are p = 2↑{31} - 512a + 1$, where
($a, r) = (1, 10), (11, 3), (19, 11), (20, 3), (29, 3), (35,
3), (55, 19), (65, 6), (95, 3), (121, 10)$. For larger $t$,
all primes $p$ of the form $2↑tq + 1$ where $q < 32$ is odd
and 2$↑{24} < p < 2↑{36}$ are given by $(p - 1, r) = (11 \cdot
2↑{21}, 3), (25 \cdot 2↑{20}, 3), (27 \cdot 2↑{20}, 5), (25
\cdot 2↑{22}, 3), (27 \cdot 2↑{22}, 7), (5 \cdot 2↑{25}, 3),
(7 \cdot 2↑{25}, 3), (7 \cdot 2↑{26}, 3), (27 \cdot 2↑{26},
13), (15 \cdot 2↑{27}, 31), (17 \cdot 2↑{27}, 3), (3 \cdot 2↑{30},
5), (13 \cdot 2, ↑{28}, 3), (29 \cdot 2↑{27}, 3), (23 \cdot
2↑{29}, 5)$. Some of the latter primes can be used with $\omega
= 2↑e$ for appropriate small $e$.

\ansno 15. (a) The hint follows by integration and induction.
Let $f↑{(n)}(\theta )$ take on all values between $A$ and $B$
inclusive, as $\theta$ varies from min($x↓0, \ldotss , x↓n)$
to max($x↓0, \ldotss , x↓n)$. Replacing $f↑{(n)}$ by these bounds,
in the stated integral, yields $A/n! ≤ f(x↓0, \ldotss , x↓n)
≤ B/n!$.\xski( (b) It suffices to prove this for $j = n$. Let $f$
be Newton's interpolation polynomial, then $F↑{(n)}$ is the
constant $n! α↓n$.

\ansno 16. Carry out the multiplications and additions of (43)
as operations on polynomials. (The special case $x↓0 = x↓1 =
\cdots = x↓n$ is considered in exercise 2. We have used this
method in step C8 of Algorithm 4.3.3C.)

\ansno 17. T. M. Vari has shown that $n - 1$ multiplications
are necessary, by proving that $n$ are necessary to compute
$x↑{2}↓{1} + \cdots + x↑{2}↓{n} [$Cornell Computer Science report
120 (Jan. 1972)].

\ansno 18. $α↓0 = {1\over 2}(u↓3/u↓4 + 1), β = u↓2/u↓4 - α↓0(α↓0
- 1), α↓1 = α↓0β - u↓1/u↓4, α↓2 = β - 2α↓1, α↓3 = u↓0/u↓4 -
α↓1(α↓1 + α↓2), α↓4 = u↓4$.

\ansno 19. Since $α↓5$ is the leading coefficient, we may assume
without loss of generality that $u(x)$ is monic (i.e., $u↓5
= 1)$. Then $α↓0$ is a root of the cubic equation 40$z↑3 - 24u↓4z↑2
+ (4u↑{2}↓{4} + 2u↓3)z + (u↓2 - u↓3u↓4) = 0$; this equation
always has at least one real root, and it may have three. Once
$α↓0$ is determined, we have $α↓3 = u↓4 - 4α↓0, α↓1 = u↓3 -
4α↓0α↓3 - 6α↑{2}↓{0}, α↓2 = u↓1 - α↓0(α↓0α↓1 + 4α↑{2}↓{0}α↓3
+ 2α↓1α↓3 + α↑{3}↓{0}), α↓4 = u↓0 - α↓3(α↑{4}↓{0} + α↓1α↑{2}↓{0}
+ α↓2)$.

For the given polynomial we are to solve the cubic
equation 40$z↑3 - 120z↑2 + 80z = 0$; this leads to three solutions
($α↓0, α↓1, α↓2, α↓3, α↓4, α↓5) = (0, -10, 13, 5, -5, 1), (1,
-20, 68, 1, 11, 1), (2, -10, 13, -3, 27, 1)$.

\ansno 20.                   LDA \quad |tab X|tab FAD\quad |tab
-α$↓1-\qquad ⊗⊗FADD⊗=α↓3=⊗FMUL⊗TEMP2\cr
⊗STA⊗TEMP1⊗FADD⊗=α↓2=\cr
⊗FADD⊗=α↓0-α↓3=⊗\phi \mu \theta λ⊗\tau ε\mu π??\cr
⊗STA⊗TEMP2⊗FADD⊗=α↓4=\cr
⊗FMUL⊗TEMP2⊗FMUL⊗=α↓5=\cr
⊗STA⊗EEMP2$
|qleft \cr

\ansno 21. $z = (x + 1)x - 2, w = (x + 5)z + 9, u(x) =
(w + z - 8)w - 8$; or $z = (x + 9)x + 26, w = (x - 3)z + 73,
u(x) = (w + z - 24)w - 12$.

\ansno 22. α$↓6 = 1, α↓0 = -1, α↓1 = 1, β↓1 = -2, β↓2 = -2,
β↓4 = 1, α↓3 = -4, α↓2 = 0, α↓4 = 4, α↓5 = -2$. We form $z =
(x - 1)x + 1, w = z + x$, and $u(x) = \biglp (z - x - 4)w +
4\bigrp z - x$.

\ansno 23. (a) We may use induction on $n$; the result is trivial
if $n < 2$. If $f(0) = 0$, then the result is true for the polynomial
$f(z)/z$, so it holds for $f(z)$. If $f(iy) = 0$ for some real
$y ≠ 0$, then $g(\pm iy) = h(\pm iy) = 0$; since the result
is true for $f(z)/(z↑2 + y↑2)$, it holds also for $f(z)$. Therefore
we may assume that $f(z)$ has no roots whose real part is zero.
Now the net number of times the given path circles the origin
is the number of roots of $f(z)$ inside the region, which is
at most 1. When $R$ is large, the path $f(Re↑{it})$ for $π/2
≤ t ≤ 3π/2$ will circle the origin clockwise approximately $n/2$
times; so the path $f(it)$ for $-R ≤ t ≤ R$ must go counterclockwise
around the origin at least $n/2 - 1$ times. For $n$ even, this
implies that $f(it)$ crosses the imaginary axis at least $n
- 2$ times, and the real axis at least $n - 3$ times; for $n$
odd, $f(it)$ crosses the real axis at least $n - 2$ times and
the imganary axis at least $n - 3$ times. These are roots respectively
of $g(it) = 0, h(it) = 0$.

(b) If not, $g$ or $h$ would have a root of the
form $a + bi$ with $a ≠ 0$ and $b ≠ 0$. But this would imply
the existence of at least three other such roots, namely $a
- bi$ and $-a \pm bi$, while $g(z), h(z)$ have at most $n$ roots.

|qleft \3skip ff?????????|newtype W58320---Compu
%folio 832 galley 8 (C) Addison-Wesley 1978	-
ter Programming\quad (Knuth/Addison-Wesley)\quad Answers\quad
f. 832\quad g. 8d
\ansno 24. The roots of $u$ are -7, -3 \pm $i, -2 \pm i, -1$;
permissible values of $c$ are $2$ and 4 ({\sl not} 3, since
$c = 3$ makes the sum of the roots equal to zero). Case 1, $c
= 2: p(x) = (x + 5)(x↑2 + 2x + 2)(x↑2 + 1)(x - 1) = x↑6 + 6x↑5
+ 6x↑4 + 4x↑3 - 5x↑2 - 2x - 10; q(x) = 6x↑2 + 4x - 2 = 6(x +
1)(x - {1\over 3})$. Let $α↓2 = -1, α↓1 = {1\over 3}; p↓1(x)
= x↑4 + 6x↑3 + 5x↑2 - 2x - 10 = (x↑2 + 6x + {16\over 3})(x↑2
- {1\over 3}) - {74\over 9}; α↓0 = 6, β↓0 = {16\over 3}, β↓1
= -{74\over 9}$. Case 2, $c = 4:$ A similar analysis gives $α↓2
= 9, α↓1 = -3, α↓0 = -6, β↓0 = 12, β↓1 = -26$.

\ansno 25. $β↓1 = α↓2, β↓2 = 2α↓1, β↓3 = α↓7, β↓4 = α↓6, β↓5
= β↓6 = 0, β↓7 = α↓1, β↓8 = 0, β↓9 = 2α↓1 - α↓8$.

\ansno 26≡. (a) $λ↓1 = α↓1 \times λ↓0, λ↓2 = α↓2 + λ↓1, λ↓3
= λ↓2 \times λ↓0, λ↓4 = α↓3 + λ↓3, λ↓5 = λ↓4 \times λ↓0, λ↓6
= α↓4 + λ↓5$.\xskip (b) $\kappa ↓1 = 1 + β↓1x, \kappa ↓2 = 1 + β↓2\kappa
↓1x, \kappa ↓3 = 1 + β↓3\kappa ↓2x, u(x) = β↓4\kappa ↓3 = β↓1β↓2β↓3β↓4x↑3
+ β↓2β↓3β↓4x↑2 + β↓3β↓4x + β↓4$.\xskip (c) If any coefficient is zero,
the coefficient of $x↑3$ must also be zero in (b), while (a)
yields an arbitrary polynomial $α↓1x↑3 + α↓2x↑2 + α↓3x + α↓4$
of degree ≤3.

\ansno 27. Otherwise there would be a nonzero polynomial $f(q↓n,
\ldotss , q↓1, q↓0)$ with integer coefficients such that $qn
\cdot f(q↓n, \ldotss , q↓1, q↓0) = 0$ for all sets $(q↓n, \ldotss
, q↓0)$ of real numbers. This cannot happen, since it is easy
to prove by induction on $n$ that a nonzero polynomial always
takes on some nonzero value. (However, this result is false
for$finite$ fields in place of the real numbers.)

\ansno 28. The indeterminate quantities $α↓1, \ldotss , α↓s$
form an algebraic basis for $Q[α↓1, \ldotss , α↓s]$, where $Q$
is the field of rational numbers. Since $s + 1$ is greater than
the number of elements in a basis, the polynomials $f↓j(α↓1,
\ldotss , α↓s)$ are algebraically dependent; this means that
that there is a nonzero polynomial $g$ with rational coefficients
such that $g\biglp f↓0(α↓1, \ldotss , α↓s), \ldotss , f↓s(α↓1,
\ldotss , α↓s)\bigrp$ is identically zero.

\ansno 29. Given $j↓0, \ldotss , j↓t \in \{0, 1, \ldotss , n\}$,
there are nonzero polynomials with integer coefficients such
that $g↓j(q↓j|infinf 0, \ldotss , q↓j|infinf t) = 0$ for all
($q↓n, \ldotss , q↓0)$ in $R↓j, 1 ≤ j ≤ m$. The product $g↓1g↓2
\ldotss g↓m$ is therefore zero for all $(q↓n, \ldotss , q↓0)$
in $R↓1 ∪ \cdots ∪ R↓m$.

\ansno 30. Starting with the construction in Theorem M\null, we will
prove that $m↓2 + (1 - \delta ↓{0m}|infinf 1)$ of the $β$'s
may effectively be eliminated: If $\theta ↓i$ corresponds to
a parameter multiplication, we have $\mu ↓i = β↓{2i-1} \times
(T↓{2i} + β↓{2i})$; add $cβ↓{2i-1}β↓{2i}$ to each $β↓j$ for
which $c\mu ↓i$ occurs in $T↓j$, and replace $β↓{2i}$ by zero.
This removes one aprameter multiplication. If $\mu ↓i$ is the
first chain multiplication, then $\mu ↓i$ is the first chain
multiplication, then $\mu ↓i = (\gamma ↓1x + \theta ↓1 + β↓{2i-1})
\times (\gamma ↓{2x} + \theta ↓2 + β↓{2i})$, where $\gamma ↓1,
\gamma ↓2, \theta ↓1, \theta ↓2$ are polynomials in $β↓1, \ldotss
, β↓{2i-2}$ with integer coefficients. Here $\theta ↓1$ and
$\theta ↓2$ can be ``absorbed'' into $β↓{2i-1}$ and $β↓{2i}$,
respectively, so we may assume that $\theta ↓1 = \theta ↓2 =
0$. Now add $cβ↓{2i-1}β↓{2i}$ to each $β↓j$ for which $c\mu
↓i$ occurs in $T↓j$; add $β↓{2i-1}\gamma ↓2/\gamma ↓1$ to $β↓{2i}$;
and set $β↓{2i-1}$ to zero. The result set is unchanged by this
elimination of $β↓{2i-1}$, except for the values of $α↓1, \ldotss
, α↓s$ such that $\gamma ↓1$ is zero. \biglp This proof is essentially
due to V. Ya. Pan, {\sl Russian Mathematical Surveys} {\bf 21}
(1966), 105--136.\bigrp The latter case can be handled as in
the proof of Theorem A\null, since the polynomials with $\gamma ↓1
= 0$ can be evaluated by eliminating $β↓{2i}$ (as in the first
construction, where $\mu ↓i$ corresponds to a parameter multiplication).

\ansno 31. Otherwise we could add one parameter multiplication
as a final step, and violate Theorem C\null.\xskip (The exercise is an
improvement over Theorem A\null, in this special case, since there
are only $n$ degrees of freedom in the coefficients of a monic
polynomial of degree $n.)$

\ansno 32. λ$↓1 = λ↓0 \times λ↓0, λ↓2 = α↓1 \times λ↓1, λ↓3
= α↓2 + λ↓2, λ↓4 = λ↓3 \times λ↓1, λ↓5 = α↓3 + λ↓4$. We need
at least three multiplications to compute $u↓4x↑4$ (see Section
4.6.3), and at least two additions by Theorem A.

\ansno 33. We must have $n + 1 ≤ 2m↓1 + m↓2 + \delta ↓{0m}|infinf
1$, and $m↓1 + m↓2 = (n + 1)/2$; so there are no parameter multiplications.
Now the first $λ↓i$ whose leading coefficient (as a polynomial
in $x)$ is not an integer must be obtained by a chain addition;
and there must be at least $n + 1$ parameters, so there are
at least $n + 1$ parameter additions.

\ansno 34. Transform the given chain step by step, and also
define the ``content'' $c↓i$ of $λ↓i$, as follows: (Intuitively,
$c↓i$ is the leading coefficient of $λ↓i.)$ Define $c↓0 = 1$.
\xskip (a) If the step has the form $λ↓i = α↓j + λ↓k$, replace it by
$λ↓i = β↓j = α↓j/c↓k$; and define $c↓i = c↓k$.\xskip (b) If the step
has the form $λ↓i = α↓j - λ↓k$, replace it by $λ↓i = β↓j + λ↓k$,
where $β↓j = α↓j/c↓k$; and define$c↓i = c↓k$. (b) If the step
has the form $λ↓i = α↓j - λ↓k$, replace it by $λ↓i = β↓j + λ↓k$,
where $β↓j = -α↓j/c↓k$; and define $c↓i = -c↓k$.\xskip (c) If the
step has the form $λ↓i = α↓j \times λ↓k$, replace it by $λ↓i
= λ↓k$ (the step will be deleted later); and define $c↓i = α↓jc↓k$.\xskip
(d) If the step has the form $λ↓i = λ↓j \times λ↓k$, leave it
unchanged; and define $c↓i = c↓jc↓k$.

After this process is finished, delete all steps
of the form $λ↓i = λ↓k$, replacing $λ↓i$ by $λ↓k$ in each future
step that uses $λ↓j$. Then add a final step $λ↓{r+1} = β \times
λ↓r$, where $β = c↓r$. This is the desired scheme, since it
is easy to verify that the new $λ↓i$ are just the old ones divided
by the factor $c↓i$. The $β$'s are given functions of the $α$'s;
division by zero is no problem, because if any $c↓k = 0$ we
must have $c↓r = 0$ (hence the coefficient of $x↑n$ is zero),
or else $λ↓k$ never contributes to the final result.

\ansno 35. Since there are at least five parameter steps, the
result is trivial unless there is at least one parameter multiplication;
considering the ways in which three multiplications can form
$u↓4x↑4$, we see that there must be one parameter multiplication
and two chain multiplications. Therefore the four addition-subtractions
must each be parameter steps, and exercise 34 applies. We can
now assume that only additions are used, and that we have a
chain to compute a general {\sl monic} fourth degree polynomial
with {\sl two} chain multiplications and four parameter additions.
The only possible scheme of this type that calculates a fourth
degree polynomial has the form
$$$λ↓1 = α↓1 + λ↓$
0|qctr \4skip λ$↓2 = α↓2 + λ↓$
0|qctr \4skip λ$↓3 = λ↓1 \times λ↓$
2|qctr \4skip λ$↓4 = α↓3 + λ↓$
3|qctr \4skip λ$↓5 = α↓4 + λ↓$
3|qctr \4skip λ$↓6 = λ↓4 \times λ↓$
5|qctr \4skip λ$↓7 = α↓5 + λ↓$
6|qctr \9skip Actually this chain has one addition too many,
but any correct scheme can be put into this form if we restrict
some of the $α$'s to be the functions of the others. Now $λ↓7$
has the form $(x↑2 + Ax + B)(x↑2 + Ax + C) + D = x↑4 + 2Ax↑3
+ (E + A↑2)x↑2 + EA↓x + F$, where $A = α↓1 + α↓2, B = α↓1 +
α↓2, B = α↓1α↓2 + α↓3, C = α↓1α↓2 + α↓4, D = α↓6, E = B + C,
F = BC + D$; and since this involves only three independent
parameters it cannot represent a general monic fourth-degree
polynomial.

|qleft \3skip $|tab λ↓1 |tab = α↓1 + λ↓0\qquad \qquad |tab λ↓1
|tab = α↓1 + λ↓0⊗\4skip ⊗λ↓2⊗= α↓2 + λ↓0⊗λ↓2⊗= α↓2 + λ↓0\cr
\4skip ⊗λ↓3⊗= 8↓1 \times λ↓2⊗λ↓3⊗= λ↓1 \times λ↓2\cr
\4skip ⊗λ↓4⊗= α↓3 + λ↓0⊗λ↓4⊗= α↓3 + λ↓3\cr
\4skip ⊗λ↓5⊗= α↓4 + λ↓3⊗λ↓5⊗= α↓4 + λ↓3\cr
\4skip ⊗λ↓6⊗= λ↓4 \times λ↓5⊗λ↓6⊗= λ↓4 \times λ↓5\cr
\4skip ⊗λ↓7⊗= α↓5 + λ↓6⊗λ↓7⊗= α↓5 + λ↓3\cr
\4skip ⊗λ↓8⊗= α↓6 + λ↓6⊗λ↓8⊗= α↓6 + λ↓6\cr
\4skip ⊗λ↓9⊗= λ↓7 \times λ↓8⊗λ↓9⊗= λ↓7 \times λ↓8\cr
\4skip ⊗λ↓{10}⊗= α↓7 + λ↓9⊗λ↓{10}⊗= α↓7 + λ↓9\cr
\9skip$ where, as in exercise 35, an extra addition has been
inserted to cover a more general case. Neither of these schemes
can calculate a general sixth-degree monic polynomial, since
the first case is a polynomial of the form
$$($x↑3 + Ax↑2 + Bx + C)(x↑3 + Ax↑2 + Bx + D) + E$,
|qctr \9skip and in the second case (cf.\ exercise 35) is a polynomial
of the form
$$\biglp $x↑4 + 2Ax↑3 + (E + A↑2)x↑2 + EAx + F\bigrp (x↑2 +
Ax + G) + H$;
|qctr \9skip both of these involve only five independent parameters.

\ansno 37. Let $u↑{[0]}(x) = u↓nx↑n + u↓{n-1}x↑{n-1} + \cdots
+ u↓0, v↑{[0]}(x) = x↑n + v↓{n-1}x↑{n-1} + \cdots + v↓0$. For
$1 ≤ j ≤ n$, divide $u[↑{j-1]}(x)$ by the monic polynomial $v↑{[j-1]}(x)$,
obtaining $u↑{[j-1]}(x) = α↓jv↑{[j-1]}(x) + β↓jv↑{[j]}(x)$.
Assume that a monic polynomial $v↑{[j]}(x)$ of degree $n - j$
exists satisfying this relation; this will be true for almost
all rational functions. Let $u↑{[j]}(x) = v↑{[j-1]}(x) - xv↑{[j]}(x)$.
These definitions imply that deg($↑{u]}) < 1$, so we may let
$α↓{n+1} = u↑{[n]}(x)$.

For the given rational function we have
$$$|tab \quad α↓j\quad |tab \quad β↓j\quad |tab v↑{[j]}(x)\quad
|tab \quad u↑{[j]}(x) \quad |tab ⊗\3skip 1⊗2⊗x + 5⊗3x + 19\cr
3⊗4⊗1⊗5\cr
\9skip$ so $u↑{[0]}(x)/v↑{[0]}(x) = 1 + 2/\biglp x + 3 + 4/(x
+ 5)\bigrp $.
|qleft ${\sl Notes:}$ A general rational function of the stated
form has $2n + 1$ ``degrees of freedom,'' in the sense that
it can be shown to have $2n + 1$ essentially independent parameters.
If we generalize polynomial chains to ``arithmetic chains,''
which allow division operations as well as addition, subtraction,
and multiplication, we can obtain the following results with
slight modifications to the proofs of Theorems A and M\null: {\sl
An arithmetic chain with q addition-subtraction steps has at
most q + 1 degrees of freedom. An arithmetic chain with m multiplication-division
steps has at most 2m + 1 degrees of freedom.} Therefore an arithmetic
chain that computes almost all ration functions of the stated
form must have at least $2n$ addition-subtractions, and $n$
multiplication-divisions; the method in this exercise is ``optimal.''
|qleft ff??????|newtype W58320---Computer Programming\quad (Knuth/Add
%folio 835 galley 9a (C) Addison-Wesley 1978	-
ison-Wesley)\quad Answers\quad f. 835\quad g. 9d
\ansno 38. The theorem is certainly true if $n = 0$. Assume
that $n$ is positive, and that a polynomial chain computing
$P(x; u↓0, \ldotss , u↓n)$ is given, where each of the parameters
$α↓j$ has been replaced by a real number. Let $λ↓i = λ↓j \times
λ↓k$ be the first chain multiplication step that involves one
of $u↓0, \ldotss , u↓n$; such a step must exist because of the
rank of $A$. Without loss of generality, we may assume that
$λ↓j$ involves $u↓n$; thus, $λ↓j$ has the form $h↓0u↓0 + \cdots
+ h↓nu↓n + f(x)$, where $h↓0, \ldotss , h↓n$ are real, $h↓n ≠
0$, and $f(x)$ is a polynomial with real coefficients. \biglp
The $h$'s and the coefficients of $f(x)$ are derived from the
values assigned to the $α$'s.\bigrp

 Now change step $i$ to $λ↓i = α \times λ↓k$, where
$α$ is an arbitrary real number. (We could take $α = 0$; general
$α$ is used here merely to show that there is a certain amount
of flexibility available in the proof.) Add further steps to
calculate
$$$λ = \biglp α - f(x) - h↓0u↓0 - \cdots - h↓{n-1}u↓{n-1}\bigrp
/h↓n$;
|qctr \9skip these new steps involve only additions and parameter
multiplications (by suitable new parameters). Finally, replace
$λ↓{-n-1} = u↓n$ everywhere in the chain by this new element
$λ$. The result is a chain that calculates
$$$Q(x; u↓0, \ldotss , u↓{n-1}) = P(x; u↓0, \ldotss , u↓{n-1},
(α - f(x) - h↓0u↓0 - \cdots - h↓{n-1}u↓{n-1})/h↓n\bigrp $;

|qleft \9skip and this chain has one less chain multiplication.
The proof will be complete if we can show that $Q$ satisfies
the hypotheses. The quantity \biglp $α - f(x)\bigrp /h↓n$ leads
to a possibly increased value of $m$, and a new vector $B↑\prime
$. If the columns of $A$ are $A↓0, A↓1, \ldotss , A↓n$ (these
vectors being linearly independent over the reals), the new
matrix $A↑\prime$ corresponding to $Q$ has the column vectors
$$$A↓0 - (h↓0/h↓n)A↓n,\qquad \ldotss ,\qquad A↓{n-1} - (h↓{n-1}/h↓n)A↓n$,
|qctr \9skip plus perhaps a few rows of zeros to account for
an increased value of $m$, and these columns are clearly also
linearly independent. By induction, the chain that computes
$Q$ has at least $n - 1$ chain multiplications, so the original
chain has at least $n$.

(This proof of Ostrowski's conjecture is taken
from Garsia's unpublished notes. An independent proof, which
shows further that the possibility of division gives no improvement,
was published by Pan in his survey paper cited in connection
with exercise 30. Generalizations to the computation of several
polynomials in several variables, with and without various kinds
of preconditioning, have been given by S. Winograd, {\sl Comm.\
Pure and Applied Math.\ \bf 23} (1970), 165--179. In particular,
Winograd showed that at least $mn$ multiplications are needed
to multiply a general $m \times n$ matrix by the vector $(x↓1,
\ldotss , x↓n)$, and at least \lfloor ${1\over 2}$$mn\rfloor$
of these do not depend only on the entries of the matrix or
only on the entries of the vector.

\ansno 39. By induction on $m$. Let $w↓m(x) = x↑{2m} + u↓{2m-1}x↑{2m-1}
+ \cdots + u↓0, w↓{m-1}(x) = x↑{2m-2} + v↓{2m-3}x↑{2m-3} + \cdots
+ v↓0, a = α↓1 + \gamma ↓m, b = α↓m$, and let $f(r) = \sum ↓{i,j≥0}
(-1)↑{i+j}({i+j\atop j})u↓{r+i+2j}a↑ib↑j$. It follows that $v↓r
= f(r + 2)$ for $r ≥ 0$, and $\delta ↓m = f(1)$. If $\delta
↓m = 0$ and $a$ is given, we have a polynomial of degree $m
- 1$ in $b$, with leading coefficient $\pm (u↓{2m-1} - ma) =
\pm (\gamma ↓2 + \cdots + \gamma ↓m - m\gamma ↓m)$.

In Motzkin's unpublished notes he arranged to
make $\delta ↓k = 0$ almost always, by choosing $\gamma$ 's
so that this leading coefficient is |spose ??=0 when $m$ is
even and =0 when $m$ is odd; then we almost always can let $b$
be a (real) root of an odd-degree polynomial.

\ansno 40. No; S. Winograd found a way to compute all polynomials
of degree 13 with only 7 (possibly complex) multiplications
[{\sl Comm.\ Pure and Applied Math.\ \bf 25} (1972), 455--457].
L. Revah found schemes that evaluate almost all polynomials
of degree $n ≥ 9$ with $\lfloor n/2\rfloor + 1$ (possibly complex)
multiplications {\sl [SIAM J. Computing} {\bf 4} (1975), 381--392];
for $n = 9$ her scheme is $u(x) = \biglp v(x)(x + α) - \biglp
v(x) + β\bigrp (x + \gamma ) + \delta \bigrp \cdot \biglp v(x)(x
+ α) + ε\bigrp + \xi $, where $v(x)$ is a monic polynomial of
degree 4. By appending sufficiently many additions (cf.\ exercise
39), the ``almost all'' and ``possibly complex'' provisos disappear.

\ansno 41. $a(c + d) - (a + b)d + i\biglp a(c + d) + (b - a)c\bigrp
$; or (cf.\ Eq.\ 4.3.3 with $2↑n$ replaced by $i!) ac - bd + i\biglp
(a + b)(c + d) - ac - bd\bigrp $; etc. [Beware numerical instability.]

\ansno 42. (a) Let $π↓1, \ldotss , π↓m$ be the $λ↓$i's that correspond
to chain multiplications; then $π↓i = P↓{2i-1} \times P↓{2i}$
and $u(x) = P↓{2m+1}$, where each $P↓j$ has the form $β↓j +
β↓{j0}x + β↓{j1}π↓1 + \cdots + β↓{jr(j)}π↓{r(j)}$, where $r(j)
≤ \lceil j/2\rceil - 1$ and each of the $β↓j$ and $β↓{jk}$ is
a polynomial in the $α$'s with integer coefficients. We can
systematically modify the chain (cf.\ exercise 30) so that $β↓j
= 0$ and $β↓{jr(j)} = 1$, for 1 ≤ $j ≤ 2m$; furthermore we can
assume that $β↓{30} = 0$. The result set now has at most $m
+ 1 + \sum ↓{1≤j≤2m} (\lceil j/2\rceil - 1) = m↑2 + 1$ degrees
of freedom.

(b) Any such polynomial chain with at most $m$
chain multiplications can be simulated by one with the form
considered in (a), except that now we let $r(j) = \lceil j/2\rceil
- 1$ for 1 ≤ j ≤ $2m + 1$, and we do not assume that $β↓{30}
= 0$ or that $β↓{jr(j)} = 1$ for $j ≥ 3$. This single canonical
form involves $m↑2 + 2m β$'s. As the $α$'s run thru all integers
and as we run through all chains, the $β$'s run through at most
$2↑m|supsup 2↑{+2m}$ sets of values mod 2, hence the result
set does also. In order to obtain all $2↑n$ polynomials of degree
$n$ with 0--1 coefficients, we need $m↑2 + 2m ≥ n$.

(c) Set $m ← \lfloor \sqrt{n}\rfloor$ and compute
$x↑2, x↑3, \ldotss , x↑m$. Let $u(x) = u↓{m+1}(x)x↑{(m+1)m} +
\cdots + u↓1(x)x↑m + u↓0(x)$, where each $u↓j(x)$ is a polynomial
of degree $≤m$ with integer coefficients (hence it can be evaluated
without any more multiplications). Now evaluate $u(x)$ by rule
(2) as a polynomial in $x↑m$ with known coefficients. (The number
of additions used is approximately the sum of the absolute values
of the coefficients, so this algorithm is efficient on 0--1
polynomials. Paterson and Stockmeyer also gave another algorithm
that uses about $\sqrt{2n}$ multiplications.

\qquad Reference: {\sl IEEE Symp.\ Switching and
Automata Theory} {\bf 12} (1971), 140--143. R. J. Lipton has
found 0--1 polynomials that require $c|spose ↑4\sqrt{n}/$log
$n$ chain multiplications even after complex preconditioning
[{\sl IEEE Symp.\ Found.\ Comp.\ Sci.\ \bf 16} (1975), 6--10].

\ansno 43. When $a↓i = a↓j + a↓k$ is a step in some optimal
addition chain for $n + 1$, compute $x↑i = x↑jx↑k$ and $p↓i↓=
p↓kx↑j + p↓j$, where $p↓i = x↑{i-1} + \cdots + x + 1$; omit
the final calculation of $x↑{n+1}$. We save one multiplication
whenever $a↓k = 1$, in particular when $i = 1$. (|newtype Cf.\
exercise 4.6.3--31 with $ε = {1\over 2}.)$

%folio 840 galley 9b (C) Addison-Wesley 1978
|qleft \24skip |newtype {\:r SECTION 4.7

\ansno 1. Find the first nonzero coefficient
$V↓m$, as in (4), and divide both $U(z)$ and $V(z)$ by shifting
$z↑m$ (shifting the coefficients $m$ places to the left). The
quotient will be a power series iff $U↓0 = \cdots = U↓{m-1}
= 0$.

\ansno 2. $V↑{n+1}↓{0}W↓n = V↑{n}↓{0}U↓n - (V↑{1}↓{0}W↓0)(V↑{n-1}↓{0}V↓n)
- (V↑{2}↓{0}W↓1)(V↑{n-2}↓{0}V↓{n-1}) - \cdots - (V↑{n↓{0Wn-1})(V↑{0}↓{0}V↓1)$.
Thus, we start by replacing $(U↓j, V↓j)$ by $(V↑{j}↓{0}U↓j,
V↑{j-1}↓{0}V↓j)$ for $j ≥ 1$, then set $W↓n ← U↓n - \sum ↓{0≤k<n}
W↓kV↓{n-k}$ for $n ≥ 0$, finally replace $W↓j$ by $W↓j/V↑{j+1}↓{0}$
for $j ≥ 0$. Similar techniques can be used for other algorithms
in this section.

\ansno 3. Yes. When $α = 0$, it is easy to prove by induction
that $W↓1 = W↓2 = \cdots = 0$. When $α = 1$, we find $W↓n =
V↓n$, by the ``cute'' identity
$$\sum ↓{$1≤k≤n}\left({k - (n - k)\over n}}V↓kV↓{n-k} = V↓0V↓n$.

\ansno 4. If $W(z) = e↑{V(z)}$, then $W↑\prime (z)
= V↑\prime (z)W(z)$; we find $W↓0 = 1$, and
$$$W↓n = \sum ↓{1≤k≤n} {k\over n} V↓kW↓{n-k},\qquad$ for\qquad
$n ≥ 1$.
|qctr \9skip If $W(z) =$ ln\biglp $1 + V(z)\bigrp $, then $W↑\prime
(z) + W↑\prime (z)V(z) = V↑\prime (z)$; the rule is $W↓0 = 0$,
and $W↓1 + 2W↓2z + \cdots = V↑\prime (z)/\biglp 1 + V(z)\bigrp
$.

(By exercise 6, the logarithm can be obtained
to order $n$ in $O(n$ log $n)$ operations. R. P. Brent observes
that exp\biglp $V(z)\bigrp$ can also be calculated with this
asymptotic speed by applying Newton's method to $f(x) =$ ln
$x - V(z)$; therefore \biglp 1 + $V(z)\bigrp ↑|≤a =$ exp\biglp
$α$ ln(1 + $V(z))\bigrp$ is $O(n$ log $n)$ too. {\sl [Analytic
Computational Complexity}, ed.\ by J. F. Traub (New York: Academic
Press, 1975), \quad --\quad .])

\ansno 5. We get the original series back again. This can be
used to test a reversion algorithm.

\ansno 6. $\varphi (x) = x + x\biglp 1 - xV(z)\bigrp $, cf.\
Algorithm 4.3.3R\null. Thus after $W↓0, \ldotss , W↓{N-1}$ are known,
we input $V↓N, \ldotss , V↓{2N-1}$, compute $(W↓0 + \cdots +
W↓{N-1}z↑{N-1})(V↓0 + \cdots + V↓{2N-1}z↑{2N-1}) = 1 + R↓0z↑N
+ \cdots + R↓{N-1}z↑{2N-1} + O(z↑{2N})$, and determine $W↓N,
\ldotss , W↓{2N-1}$ by the formula $W↓N + \cdots + W↓{2N-1}z↑{N-1}
= -(W↓0 + \cdots + W↓{N-1}z↑{N-1})(R↓0 + \cdots + R↓{N-1}z↑{N-1})
+ O(z↑N). [Numer.\ Math.\ \bf 22} (1974), 341--348; this algorithm
was, in essence, first published by M. Sieveking, {\sl Computing
\bf 10} (1972), 153--156.] Note that the total time for $N$
coefficients is $O(N$ log $N)$ if we use ``fast'' polynomial
multiplication (exercise 4.6.4--14).

\ansno 7. $W↓n = ({mk\atop k})/n$ when $n = (m - 1)k + 1$, otherwise
0. (Cf.\ exercise 2.3.4.4--11.)
|qleft a???|newtype W58320---Computer Programming\quad (Knuth/Addison-Wesley)\quad
%folio 842 galley 10 (C) Addison-Wesley 1978
Answers\quad f. 842\quad g. 10d
\ansno 8. Input $G↓1$ in step L1, and $G↓n$ in step L2. In
step L4, the output should be $(U↓{n-1}G↓1 + 2U↓{n-2}G↓2 + \cdots
+ nU↓0G↓n)/n$.\xskip (The running time of the order $N↑3$ algorithm
is hereby increased by only order $N↑2$. The value $W↓1 = G↓1$
might be output in step L1.)

${\sl Note:}$ Algorithms T and N determine $V↑{-1}\biglp
U(z)|newtype )$; the algorithm in this exercise determines $G\biglp
V↑{-1}(z)\bigrp $, which is somewhat different. Of course, the
results can all be obtained by a sequence of operations of reversion
and composition (exercise 11), but it is helpful to have more
direct algorithms for each case.

\ansno 9.|zfa
 |qleft }∂\qquad |tab \quad n = 1\quad |tab \quad n = 2\quad
|tab \quad n = 3\quad |tab \quad n = 4\quad |tab \quad n = 5\quad
|tab ⊗\3skip \qquad T$↓{1n}⊗1⊗1⊗2⊗5⊗14\cr
\qquad T↓{2n}⊗⊗1⊗2⊗5⊗14\cr
\qquad T↓{3n}⊗⊗⊗1⊗3⊗ 9\cr
\qquad T↓{4n}⊗⊗⊗⊗1⊗ 4\cr
\qquad T↓{5n}⊗⊗⊗⊗⊗ 1\cr

\ansno 10. Form $y↑{1/|}≤a = x(1 + a↓1x + a↓2x↑2 + \cdotss
)↑{1/|}≤a = x(1 + c↓1x + c↓2x↑2 + \cdotss)$ by means of (9);
then revert the latter series. (See the remarks following Eq.\
1.2.11.3--11.)

\ansno 11. Set $W↓0 ← U↓0$, and set $(T↓k, W↓k) ← (V↓k, 0)$
for 1 ≤ $k ≤ N$. Then for $n = 1, 2, \ldotss , N$, do the following:
Set $W↓j ← W↓j + U↓nT↓j$ for $n ≤ j ≤ N$; and then set $T↓j
← T↓{j-1}V↓1 + \cdots + T↓nV↓{j-n}$ for $j = N, N - 1, \ldotss
, n + 1$.

Here $T(z)$ represents $V(z)↑n$. An $on-line$
power-series algorithm for this problem, analogous to Algorithm
T\null, could be constructed, but it would require about $N↑2/2$
storage locations. There is also an on-line algorithm that
solves this exercise and needs only $O(N)$ storage locations:
We may assume that $V↓1 = 1$, if $U↓k$ is replaced by $U↓kV↑{k}↓{1}$
and $V↓k$ is replaced by $V↓k/V↓1$ for all $k$. Then we may
revert $V(z)$ by Algorithm L\null, using its output as input to the
algorithm of exercise 8 with $G↓1 = U↓1, G↓2 = U↓2$, etc., thus
computing $U\biglp (V↑{-1})↑{-1}(z)\bigrp - U↓0$.

Brent and Kung have constructed several algorithms
that are asymptotically faster. For example, we can evaluate
$U(x)$ for $x = V(z)$ by a slight variant of exercise 4.6.4--42(c),
doing about 2\sqrt{$n}$ chain multiplications of cost $M(n)$
and about $n$ parameter multiplications of cost $n$; the total
time is therefore $O\biglp \sqrt{n}M(n) + n↑2\bigrp = O(n↑2)$.
A still faster method can be based on the identity $U\biglp
V↓0(z) + z↑mV↓1(z)\bigrp = U\biglp V↓0(z)\bigrp + z↑mU↑\prime
\biglp V↓0(z)\bigrp V↓1(z) + z↑{2m}U??\biglp V↓0(z)\bigrp V↓1(z)\bigrp
V↓1(z)↑2/2! + \cdotss$, extending to about $n/m$ terms, where
we choose $m \approx \sqrt{n/$log $n}$; the first term $U\biglp
V↓0(z)\bigrp$ is evaluated in $O\biglp mn($log $n)\bigrp ↑2)$
operations using a method somewhat like that in exercise 4.6.4--43,
and \biglp since we can go from $U↑{(k)}\biglp V↓0(z)\bigrp$
to $U↑{(k+|}≤n↑)\biglp V↓0(z)\bigrp$ in $O(n$ log $n)$ operations
by differentiating and dividing by $V↑\prime↓{1}(z)\bigrp$
the entire procedure takes $O\biglp mn($log $n)↑2 + (n/m)n$
log $n) = O(n$ log $n)↑{3/2}$ operations.

\ansno 12. Polynomial division is trivial unless $m ≥ n ≥ 1$.
Assuming the latter, the equation $u(x) = q(x)v(x) + r(x)$ is
equivalent to $U(z) = Q(z)V(z) + z↑{m-n+1}R(z)$ where $U(x)
= x↑mu(x↑{-1}), V(x) = x↑nv(x↑{-1}), Q(x) = x↑{m-n}q(x↑{-1}),
R(x) = x↑{n-1}r(x↑{-1})$ are the ``reverse'' polynomials of
$u, v, q$, and $r$.

To find $q(x)$ and $r(x)$, compute the first $m
- n + 1$ coefficients of the power series $U(z)/V(z) = W(z)
+ O(z↑{m-n+1})$; then compute the power series $U(z) - V(z)W(z)$,
which has the form $z↑{m-n+1}T(z)$ where $T(z) = T↓0 + T↓1z
+ \cdotss$. Note that $T↓j = 0$ for all $j ≥ n$; hence $Q(z)
= W(z)$ and $R(z) = T(z)$ satisfy the requirements.

|qleft \25skip |newtype {\:s APPENDIX A

|qleft }\49skip \9skip |newtype {\:r TABLES OF
}|qright {\:r NUMERICAL QUANTITIES
}|qright \12skip |newtype {\:r Table 1
}|qctr \6skip |newtype ??M22}QUANTITIES THAT ARE FREQUENTLY
USED IN STANDARD SUBROUTINES AND IN ANALYSIS OF COMPUTER PROGRAMS.
(40 DECIMAL PLACES)
|qctr |linerule ??M32}$$
|qleft \hfill \sqrt{2} ⊗= 1.41421 35623\quad 73095 04880 16887
24209 69807 85697-\cr
\hfill \sqrt{3} ⊗= 1.73205 08075 68877 29352 74463 41505 87236
69428+\cr
\hfill \sqrt{5} ⊗= 2.23606 79774 99789 69640 91736 68731 17623
54406+\cr
\hfill \sqrt{10} ⊗= 3.16227 76601 68379 33199 88935 44432 71853
37196-\cr
\hfill \sqrt{2} ⊗= 1.25992 10498 94873 16476 72106 07278 22835
05703-\cr
\hfill \sqrt{3} ⊗= 1.44224 95703 07408 38232 16383 10780 10958
83919-\cr
\hfill \sqrt{2} ⊗= 1.18920 71150 02721 06671 74999 70560 47591
52930-\cr
\hfill ln 2 ⊗= 0.69314 71805 59945 30941 72321 21458 17656 80755+\cr
\hfill ln 3 ⊗= 1.09861 22886 68109 69139 52452 36922 52570 46475-\cr
\hfill ln 10 ⊗= 2.30258 50929 94045 68401 79914 54684 36420
76011+\cr
\hfill 1/ln 2 ⊗= 1.44269 50408 88963 40735 99246 81001 89213
74266+\cr
\hfill 1/ln 10 ⊗= 0.43429 44819 03251 82765 11289 18916 60508
22944-\cr
\hfill $π ⊗= 3.14159 26535 89793 23846 26433 83279 50288 41972-\cr
\hfill 1?? = π/180 ⊗= 0.01745 32925 19943 29576 92369 07684
88612 71344+\cr
\hfill 1/π ⊗= 0.31830 98861 83790 67153 77675 26745 02872 40689+\cr
\hfill π↑2 ⊗= 9.86960 44010 89358 61883 44909 99876 15113 53137-\cr
\hfill \sqrt{π} = \Gamma (1/2) ⊗= 1.77245 38509 05516 02729
81674 83341 14518 27975+\cr
\hfill \Gamma (1/3) ⊗= 2.67893 85347 07747 63365 56929 40974
67764 41287-\cr
\hfill \Gamma (2/3) ⊗= 1.35411 79394 26400 41694 52880 28154
51378 55193+\cr
\hfill e ⊗= 2.71828 18284 59045 23536 02874 71352 66249 77572+\cr
\hfill 1/e ⊗= 0.36787 94411 71442 32159 55237 70161 46086 74458+\cr
\hfill e↑2 ⊗= 7.38905 60989 30650 22723 04274 60575 00781 31803+\cr
\hfill \gamma ⊗= 0.57721 56649 01532 86060 65120 90082 40243
10422-\cr
\hfill$ ln $π ⊗= 1.14472 98858 49400 17414 34273 51353 05871
16473-\cr
\hfill \phi ⊗= 1.61803 39887 49894 84820 45868 34365 63811 77203+\cr
\hfill e↑|≤g ⊗= 1.78107 24179 90197 98523 65041 03107 17954
91696+\cr
\hfill e↑|≤p↑{/4} ⊗= 2.19328 00507 38015 45655 97696 59278 73822
34616+\cr
\hfill$ sin 1 ⊗= 0.84147 09848 07896 50665 25023 21630 29899
96226-\cr
\hfill cos 1 ⊗= 0.54030 23058 68139 71740 09366 07442 97660
37323+\cr
\hfill $\zeta (3) ⊗= 1.20205 69031 59594 28539 97381 61511 44999
07650-\cr
\hfill$ ln $\phi ⊗= 0.48121 18250 59603 44749 77589 13424 36842
31352-\cr
\hfill 1/$ln $\phi ⊗= 2.07808 69212 35027 53760 13226 06117
79576 77422-\cr
\hfill $-ln ln 2 ⊗= 0.36651 29205 81664 32701 24391 58232 66946
94543-\cr
\-2skip |linerule \6skip a|newtype
%folio 844 galley 11 "special italic figs in position 4" (C) Addison-Wesley 1978
W58320---Computer Programming\quad (Knuth/Addison-Wesley)\quad
Appendix\quad f. 844\quad g. 11d
$$|newtype {\:r Table 2
}|qctr \6skip |newtype QUANTITIES THAT ARE FREQUENTLY USED
IN STANDARD SUBROUTINES AND IN ANALYSIS OF COMPUTER PROGRAMS,
IN {\sl OCTAL} NOTATION. THE {\sl NAME} OF EACH QUANTITY, APPEARING
AT THE LEFT OF THE EQUAL SIGN, IS GIVEN IN DECIMAL NOTATION.
|qctr |linerule \qquad \qquad \qquad 0.1 |tab = {\sl ↑\prime.↑\prime????????
?????????? ?????????? ?????????? ?????????? ?????????? ??????????
?????????? ????????⊗\hfill }0.01 ⊗= {\sl ↑\prime.↑\prime↑\prime??↑\prime??
?????????? ????????↑\prime ?????????? ??↑\prime??↑\prime?? ??????????
????????↑\prime ?????????? ??↑\prime????}\cr
\hfill 0.001 ⊗= {\sl ↑\prime.↑\prime↑\prime↑\prime??↑\prime
?????????? ????????↑\prime ?????????? ?????????? ??????????
?????????? ↑\prime??↑\prime??↑\prime ????????\cr
\hfill }0.0001 ⊗= {\sl ↑\prime.↑\prime↑\prime↑\prime↑\prime??
?????????? ????????↑\prime ??↑\prime?????? ?????????? ????????↑\prime
????↑\prime???? ????↑\prime↑\prime?? ????????}\cr
\hfill 0.00001 ⊗= {\sl ↑\prime.↑\prime↑\prime↑\prime↑\prime↑\prime
?????????? ????????↑\prime ??↑\prime?????? ????↑\prime???? ↑\prime??↑\prime????
??????↑\prime?? ????↑\prime???? ????????\cr
\hfill }0.000001 ⊗= {\sl ↑\prime.↑\prime↑\prime↑\prime↑\prime↑\prime
↑\prime??↑\prime???? ?????????? ↑\prime???????? ?????????? ??????????
↑\prime???????? ????????↑\prime ????↑\prime??}\cr
\hfill 0.0000001 ⊗= {\sl ↑\prime.↑\prime↑\prime↑\prime↑\prime↑\prime
↑\prime↑\prime?????? ?????????? ?????????? ?????????? ??????????
?????????? ??↑\prime?????? ↑\prime??????\cr
\hfill }0.00000001 ⊗= {\sl ↑\prime.↑\prime↑\prime↑\prime↑\prime↑\prime
↑\prime↑\prime↑\prime???? ?????????? ??????↑\prime?? ↑\prime????↑\prime??
?????????? ?????????? ↑\prime???????? ????????\cr
\hfill }0.000000001 ⊗= {\sl ↑\prime.↑\prime↑\prime↑\prime↑\prime↑\prime
↑\prime↑\prime↑\prime↑\prime?? ↑\prime??????↑\prime ????????↑\prime
?????????? ?????????? ?????????? ??↑\prime?????? ????????\cr
\hfill }0.0000000001 ⊗= {\sl ↑\prime.↑\prime↑\prime↑\prime↑\prime↑\prime
↑\prime↑\prime↑\prime↑\prime↑\prime ↑\prime???????? ??????????
?????????? ?????????? ?????????? ?????????? ↑\prime??????\cr
\hfill }2 ⊗= {\sl ??.??????↑\prime?? ?????????? ?????????? ????????↑\prime
?????????? ?????????? ?????????? ?????????? ????????}\cr
\hfill 3 ⊗= {\sl ??.?????????? ?????????? ??↑\prime?????? ??????????
?????????? ??↑\prime?????? ??↑\prime?????? ????↑\prime???? ????????}\cr
\hfill 5 ⊗= {\sl ??.????↑\prime???? ?????????? ?????????? ??????↑\prime??
?????????? ????↑\prime↑\prime?? ↑\prime↑\prime?????? ????????↑\prime
????↑\prime??}\cr
\hfill 10 ⊗= {\sl ??.??????↑\prime?? ??↑\prime?????? ??????????
?????????? ↑\prime???????? ??????↑\prime?? ?????????? ??????????
????????}\cr
\hfill 2 ⊗= {\sl ??.??↑\prime??↑\prime?? ↑\prime???????? ??????????
↑\prime???????? ??↑\prime?????? ?????????? ?????????? ??????????
↑\prime??↑\prime??}\cr
\hfill 3 ⊗= {\sl ??.?????????? ??↑\prime?????? ?????????? ??????????
?????????? ?????????? ↑\prime???????? ?????????? ??↑\prime????}\cr
\hfill 2 ⊗= {\sl ??.????↑\prime???? ????↑\prime??↑\prime ??????????
?????????? ?????????? ????????↑\prime ??↑\prime?????? ↑\prime????????
????????}\cr
\hfill ln 2 ⊗= {\sl ↑\prime.?????????? ↑\prime???????? ????↑\prime????
?????????? ?????????? ↑\prime???????? ??↑\prime↑\prime↑\prime??
?????????? ????????}\cr
\hfill ln 3 ⊗= {\sl ??.↑\prime???????? ?????????? ????↑\prime↑\prime??
↑\prime???????? ????????↑\prime ????↑\prime???? ????↑\prime????
?????????? ????????}\cr
\hfill ln 3 ⊗= {\sl ??.?????????? ↑\prime???????? ??????????
??????↑\prime?? ?????????? ?????????? ????↑\prime???? ????↑\prime??↑\prime
??↑\prime????}\cr
\hfill 1/ln 2 ⊗= {\sl ??.?????????? ?????????? ??????↑\prime??
????↑\prime???? ????????↑\prime ?????????? ??↑\prime?????? ??????????
↑\prime??????}\cr
\hfill 1/ln 10 ⊗= {\sl ↑\prime.?????????? ?????????? ??????????
?????????? ?????????? ?????????? ?????????? ↑\prime??????}\cr
\hfill $π ⊗= {\sl ??.????↑\prime???? ?????????? ??↑\prime??????
??↑\prime?????? ????????↑\prime ????↑\prime??↑\prime ????↑\prime↑\prime??
??↑\prime?????? ????????}\cr
\hfill 1?? = π/180 ⊗= {\sl ↑\prime.↑\prime??↑\prime???? ??????????
?????????? ?????????? ??????↑\prime?? ?????????? ??????????
????↑\prime???? ????????}\cr
\hfill 1/π ⊗= {\sl ↑\prime???????????? ??↑\prime?????? ??????????
??↑\prime?????? ????????↑\prime ?????????? ??↑\prime?????? ??????????
??↑\prime↑\prime??}\cr
\hfill π↑2 ⊗= {\sl ??.?????????? ?????????? ?????????? ??????????
?????????? ?????????? ??↑\prime↑\prime???? ??↑\prime?????? ??????↑\prime\cr
\hfill }π = \Gamma (1/2) ⊗= {\sl |raise2 ?????????? ??????↑\prime??
?????????? ?????????? ????↑\prime???? ??↑\prime????↑\prime ??????????
????????↑\prime ????????}\cr
\hfill \Gamma (1/3) ⊗= {\sl ??.?????????? ?????????? ????↑\prime????
?????????? ??????↑\prime?? ?????????? ?????????? ↑\prime↑\prime??↑\prime??
????↑\prime??}\cr
\hfill \Gamma (2/3) ⊗= {\sl ??.?????????? ?????????? ??????????
?????????? ?????????? ?????????? ??↑\prime?????? ??????????
↑\prime??????}\cr
\hfill e ⊗= {\sl ??.????????↑\prime ????????↑\prime ??↑\prime??????
?????????? ?????????? ?????????? ↑\prime↑\prime?????? ??????????
????????}\cr
\hfill 1/e ⊗= {\sl ↑\prime.?????????? ????↑\prime???? ??????????
?????????? ?????????? ?????????? ↑\prime??????↑\prime ??????????
↑\prime??????}\cr
\hfill e↑2 ⊗= {\sl ??.??↑\prime?????? ?????????? ??????????
????????↑\prime ??????↑\prime?? ????↑\prime??↑\prime ??????????
?????????? ??↑\prime????}\cr
\hfill \gamma ⊗= {\sl ↑\prime.?????????? ????????↑\prime ??????????
↑\prime???????? ?????????? ?????????? ↑\prime??↑\prime↑\prime??
?????????? ????????}\cr
\hfill$ ln $π ⊗= {\sl ??.??????↑\prime?? ??↑\prime?????? ??????↑\prime??
?????????? ?????????? ?????????? ????????↑\prime ??????????
????↑\prime??}\cr
\hfill \phi ⊗= {\sl ??.?????????? ?????????? ?????????? ??????↑\prime??
?????????? ??????↑\prime?? ??↑\prime?????? ????????↑\prime ????↑\prime??}\cr
\hfill e↑|≤g ⊗= {\sl ??.?????????? ?????????? ?????????? ??????????
?????????? ?????????? ?????????? ?????????? ????????}\cr
\hfill e↑|≤p↑{/4} ⊗= {\sl ??.?????????? ?????????? ??????????
????????↑\prime ????????↑\prime ?????????? ?????????? ??????↑\prime??
↑\prime??????}\cr
\hfill$ sin 1 ⊗= {\sl ↑\prime.?????????? ?????????? ↑\prime????????
??????↑\prime?? ↑\prime??↑\prime???? ?????????? ?????????? ↑\prime????????
????????}\cr
\hfill cos 1 ⊗= {\sl ↑\prime.????????↑\prime ??↑\prime↑\prime????
??????↑\prime?? ?????????? ↑\prime??↑\prime???? ?????????? ????????↑\prime
??↑\prime?????? ????????}\cr
\hfill $\zeta (3) ⊗= {\sl ??.?????????? ↑\prime↑\prime↑\prime????
??↑\prime↑\prime???? ??↑\prime????↑\prime ?????????? ??????????
?????????? ??↑\prime?????? ↑\prime??????}\cr
\hfill$ ln $\phi ⊗= {\sl ↑\prime.????????↑\prime ??????????
?????????? ↑\prime???????? ??????↑\prime↑\prime ????↑\prime↑\prime??
?????????? ??↑\prime??↑\prime↑\prime ??↑\prime????}\cr
\hfill$ 1/ln $\phi ⊗= {\sl ??.↑\prime???????? ??↑\prime??????
?????????? ?????????? ?????????? ?????????? ↑\prime↑\prime??????
????????↑\prime ??↑\prime????}\cr
\hfill$ -ln ln 2 ⊗= {\sl ↑\prime.?????????? ?????????? ??????????
????????↑\prime ??????↑\prime?? ?????????? ?????????? ??????????
????↑\prime??}\cr
\-2skip |linerule \6skip ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
?? ?? ?? ?? ?? ?? ?? ?? ??

|qleft \6skip ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
?? ?? ?? ??

|qleft \6skip ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
?? ?? ?? ??

|qleft \6skip ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
?? ?? ?? ??

|qleft \6skip ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ↑\prime ↑\prime
↑\prime ↑\prime ↑\prime ↑\prime ↑\prime ↑\prime ↑\prime ↑\prime
|qleft u????????????|newtype W58320---Computer Programm
%folio 845 galley 12 (C) Addison-Wesley 1978
ing\quad (Knuth/Addison-Wesley)\quad Appendix\quad f. 845\quad
g. 12d
$$|newtype \quad For high-precision values of constants not
found in this list, see J. Peters, {\sl Ten Place Logarithms
of the Numbers from {\sl 1 to 100000}}, Appendix to Volume 1
ed.\ by M. Abramowitz and I. A. Stegun (Washington, D.C.: U.S.
Gov't Printing Office, 1964), Chapter 1.

A table of Bernoulli numbers through $B↓{250}$ appears in a paper
by D. E. Knuth and T. J. Buckholtz, {\sl Math.\ Comp.\ \bf 21} (1967),
663--688.

|qleft \12skip |newtype {\:r Table 3
}|qctr \6skip |newtype VALUES OF HARMONIC NUMBERS, BERNOULLI
NUMBERS, AND FIBONACCI NUMBERS FOR SMALL VALUES OF $n$.
|qctr |linerule |tab \qquad \quad |tab \qquad \qquad \qquad
\qquad |tab \qquad \qquad \qquad \quad |tab \qquad \qquad \qquad
\quad |tab \qquad \qquad \quad |tab \qquad \qquad |tab \qquad
\quad |tab |zfa ⊗n⊗H⊗$↓n⊗\qquad \qquad \quad B↓n⊗⊗F↓n⊗n\cr
\2skip 0⊗0⊗⊗1⊗ 0⊗ 0\cr
1⊗1⊗⊗-1/⊗2⊗ 1⊗ 1\cr
2⊗3/⊗2⊗1/⊗6⊗ 1⊗ 1\cr
2⊗3/⊗2⊗1/⊗6⊗ 1⊗ 2\cr
3⊗11/⊗6⊗0⊗⊗ 2⊗ 3\cr
4⊗25/⊗12⊗-1/⊗30⊗ 3⊗ 4\cr
5⊗137/⊗60⊗0⊗⊗ 5⊗ 5\cr
6⊗49/⊗20⊗1/⊗42⊗ 8⊗ 6\cr
7⊗363/⊗140⊗0⊗⊗13⊗ 7\cr
8⊗761/⊗280⊗-1/⊗30⊗21⊗ 8\cr
9⊗7129/⊗2520⊗0⊗⊗34⊗ 9\cr
10⊗7381/⊗2520⊗5/⊗66⊗55⊗10\cr
11⊗83711/⊗27720⊗0⊗⊗89⊗11\cr
12⊗86021/⊗27720⊗-691/⊗2730⊗144 ⊗12\cr
13⊗1145993/⊗360360⊗0⊗⊗233 ⊗13\cr
14⊗1171733/⊗360360⊗7/⊗6⊗377 ⊗14\cr
15⊗1195757/⊗360360⊗0⊗⊗610 ⊗15\cr
16⊗2436559/⊗720720⊗-3617/⊗510⊗987 ⊗16\cr
17⊗42142223/⊗12252240⊗0⊗⊗1597\quad ⊗17\cr
18⊗14274301/⊗4084080⊗43867/⊗798⊗2584\quad ⊗18\cr
19⊗275295799/⊗77597520⊗0⊗⊗4181\quad ⊗19\cr
20⊗55835135/⊗15519504⊗-174611/⊗330⊗6765\quad ⊗20\cr
21⊗18858053/⊗5173168⊗0⊗⊗10946\quad ⊗21\cr
22⊗19093197/⊗5173168⊗854513/⊗138⊗17711\quad ⊗22\cr
23⊗444316699/⊗118982864⊗0⊗⊗28657\quad ⊗23\cr
24⊗1347822955/⊗356948592⊗-236364091/⊗2730⊗46368\quad ⊗24\cr
25⊗34052522467/⊗8923714800⊗0⊗⊗75025\quad ⊗25\cr
\-2skip |linerule \3skip |newtype$ For any $x$, let $H↓x = \sum
↓{n≥1}\left({1\over n} - {1\over n + x}}$. Then
$$$$
|qctr \hfill H$↓{1/2} ⊗= 2 - 2$ ln 2,\cr
\4skip \hfill $H↓{1/3} ⊗= 3 - {1\over 2}π/\sqrt{3} - {3\over
2}$ ln 3,\cr
\4skip \hfill $H↓{2/3} ⊗= {3\over 2} + {1\over 2}π/\sqrt{3}
- {3\over 2}$ ln 3,\cr
\4skip $\hfill H↓{1/4} ⊗= 4 - {1\over 2}π - 3$ ln 2,\cr
\4skip \hfill $H↓{3/4} ⊗= {4\over 3} + {1\over 2}π - 3$ ln 2,\cr
\hfill $H↓{1/5} ⊗= 5 - {1\over 2}π\phi \sqrt{2{2 + \phi \over
5}} - {1\over 2}(3 - \phi )$ln 5 $- (\phi - {1\over 2})$ln(2
+ $\phi ),\cr
\4skip \hfill H↓{2/5} ⊗= {5\over 2} - {1\over 2}π/\phi \sqrt{2
+ \phi } - {1\over 2}(2 + \phi )$ln 5 +$ (\phi - {1\over 2})$ln(2
+ $\phi ),\cr
\4skip \hfill H↓{3/5} ⊗= {5\over 3} + {1\over 2}π/\phi \sqrt{2
+ \phi } - {1\over 2}(2 + \phi )$ln 5 +$ (\phi - {1\over 2})$ln(2
+ $\phi ),\cr
\hfill H↓{4/5} ⊗= {5\over 4} + {1\over 2}π\phi \sqrt{2{2 + \phi
\over 5}} - {1\over 2}(3 - \phi )$ln 5 $- (\phi - {1\over 2}$ln(2
+ $\phi ),\cr
\4skip \hfill H↓{1/6} = 6 - {1\over 2}π\sqrt{3} $- 2 ln 2 -
${3\over 2}$ ln 3,\cr
\4skip \hfill $H↓{5/6} ⊗= {6\over 5} + {1\over 2}π\sqrt{3} -
2$ ln 2 - ${3\over 2}$ ln 3,\cr
\9skip and, in general, when $0 < p < q$ (cf.\ exercise 1.2.9--19),
$$$H↓{p/q} = {q\over p} - {1\over 2}π$ cot ${p\over q}$ π -
ln $2q + 2\sum ↓{1≤n<q/2}$cos ${2πnp\over q}$ ln sin ${n\over
q}$ π.
|qctr \24skip |newtype {\:s APPENDIX B

|qleft }\69skip |newtype {\:r INDEX TO NOTATIONS
}|qright \51skip |newtype In the following formulas, letters
that are not further qualified have the following significance:
$$
|qctr \hfill $j, k\quad ⊗$integer-valued arithmetic expression\cr
\4skip $\hfill m, n\quad ⊗$nonnegative integer-valued arithmetic
expression\cr
\4skip \hfill $x, y, z\quad ⊗$real-valued arithmetic expression\cr
\4skip \hfill $f\quad ⊗$real-valued function\cr
\12skip |tab \qquad \qquad \qquad \qquad \quad |tab \qquad \qquad
\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad |tab
\qquad \qquad \quad |tab |zfa ⊗⊗⊗{\bf Section}\cr
{\bf Formal symbolism}\quad
 |qctr {\bf Meaning
}|qctr {\bf reference
}|qctr \cr
\-2skip |linerule $A↓n\quad ⊗$the $n$th element of linear array
$A\cr
\3skip A↓{mn}\quad ⊗$the element in row $m$, column $n$ of rectan-\cr
⊗gular array $A\cr
\3skip A[n]\quad ⊗$equivalent to $A↓n⊗ 1.1\cr
\3skip A[m, n]\quad ⊗$equivalent to $A↓{mn}⊗ 1.1\cr
\3skip V ← E\quad ⊗$give variable $V$ the value of expression
$E⊗ 1.1\cr
\3skip U ↔ V\quad ⊗$interchange the values of variables $U$
and $V⊗ 1.1\cr
\3skip (B ??2] E↓1; E↓2)\quad$
 |qright conditional expression: denotes $E↓1$ if $B$ is
 |qleft \cr
⊗true, if $B$ is false\cr
\3skip $\delta ↓{jk}\quad ⊗$Kronecker delta:$ (j = h ??2] 1;
0)⊗ 1.2.6\cr
\3skip \sum ↓{R(k)} f(k)\quad \cr
\-26skip ⊗$sum of all $f(k)$ such that $k$ is an integer and\cr
⊗relation $R(k)$ is true⊗ 1.2.3\cr
\4skip $\mathop{\prod ↓{R(k)} f(k)\quad \cr
\-25skip ⊗$product of all $f(k)$ such that $k$ is an integer\cr
⊗and relation $R(k)$ is true⊗ 1.2.3\cr
\4skip \mathop{min↓{|raise2 $R(k)} f(k)\quad \cr
\-25skip ⊗$minimum value of all $f(k)$ such that $k$ is an\cr
⊗integer and relation $R(k)$ is true⊗ 1.2.3\cr
\4skip \mathop{max↓{|raise2 $R(k)} f(k)\quad \cr
\-25skip ⊗$maximum value of all $f(k)$ such that $k$ is an\cr
⊗integer and relation $R(k)$ is true⊗ 1.2.3\cr
\4skip $j\rslash k\quad ⊗j$ divides $k: k$ mod $j = 0⊗ 1.2.4\cr
\3skip$ gcd($j, k)\quad ⊗$greatest common divisor of $j$ and
$k:\cr
⊗(j = k = 0 ??2] 0;\qquad$ \mathop{max↓{$|raise2 d\rslash j,d\rslash
k} d)⊗ 4.5.2\cr
\6skip$ lcm($j, k)\quad ⊗$least common multiple of $j$ and $k:\cr
⊗(j = k = 0 ??2] 0;\qquad$ \mathop{min↓{$|raise2 d>0??j\rslash
d,k\rslash d}⊗ 4.5.2\cr
\6skip$ det($A)\quad ⊗$determinant of square matrix $A⊗ 1.2.3\cr
\3skip A↑T\quad ⊗$transpose of rectangular array $A:\cr
\6skip ⊗A↑T[j, k] = A[k, j]⊗ 1.2.3\cr
\6skip x↑y\quad ⊗x$ to the $y$ power, $x$ positive⊗ 1.2.2\cr
\3skip $x↑k\quad ⊗x$ to the $k$th power:⊗\6skip ⊗\left($k ≥
0 ??2] \mathop{\prod ↓{0≤j<k} x;\qquad 1/x↑{-k}}⊗ 1.2.2\cr
\6skip x|spose ↑{3k}\quad ⊗x$ upper $k:\cr
\6skip ⊗\left(↓{}k ≥ 0 ??2] x(x + 1) \ldotsm (x + k - 1)\cr
\-6skip ⊗=\mathop{\prod ↓{0≤j<k} (x + j);\qquad 1/(x + k)↑{-k}}
⊗ 1.2.6\cr
\6skip |spose ↓3↑k\quad ⊗x$ lower $k:\cr
\6skip ⊗\left(↓{}k ≥ 0 ??2] x(x - 1) \ldotsm (x - k + 1)\cr
\-6skip ⊗= \mathop{\prod ↓{0≤j<k} (x - j); \cr
\6skip ⊗1/(x - k)\mathop{---↑{|lower2 -k}}↓{} = (-1)↑k(-x)|spose
↑{∩k} ⊗1.2.6\cr
\6skip n!\quad ⊗n$ factorial: 1 \cdot 2 \cdot \ldotsm \cdot $n
= n|spose ↓3↑n⊗ 1.2.5\cr
\3skip \left({x\atop k}}\quad ⊗$binomial coefficient: $(k <
0 ??2] 0; x|spose ↓3↑k/k!)⊗ 1.2.6⊗\3skip \left({n\atop n↓1,
n↓2, \ldotss , n↓m}}\quad \cr
\-26skip ⊗$multinomial coefficient,⊗\2skip ⊗$n = n↓1 + n↓2 +
\cdots + n↓m⊗1.2.6\cr
\3skip \left[{n\atop m}}\quad ⊗$Stirling number of first kind:\cr
⊗$\mathop{\sum ↓{0<k↓1<k↓2<\cdots <k↓{n-m}<n} k↓1k↓2
\ldotsm k↓{n-m}⊗ 1.2.6\cr
\3skip \left\{{n\atop m}}\quad ⊗$Stprling number of second kind:\cr
⊗$\sum ↓{1≤k↓1≤k↓2≤\cdots ≤k↓{n-m}≤m} k↓1k↓2 \ldotsm
k↓{n-m}⊗ 1.2.6\cr
\6skip \bfslash x↓1, x↓2, \ldotss , x↓n\bfslash \quad ⊗$continued
fraction:\cr
\2skip $1/\biglp x↓1 + 1/(x↓2 + 1/(\,\cdots + 1/(x↓n) . . .))\bigrp$
 |qctr 4.5.3
|qleft \cr
\3skip X \cdot Y\quad ⊗dot product of vectors $X = (x↓1, \ldotss
, x↓n)$ and\cr
⊗$Y = (y↓1, \ldotss , y↓n): x↓1y↓1 + \cdots + x↓ny↓n\cr
\3skip (\ldotsm a↓1a↓0 \cdot a↓{-1} . . .)↓b\quad ⊗$radix$-b$
positional notation: $\sum ↓k a↓kb↑k⊗ 4.1\cr
\3skip \{a | R(a)\}\quad ⊗$set of all $a$ for which the relation
$R(a)$ is true\cr
\3skip $\{a↓1, \ldotss , a↓n\}\quad ⊗$the set \{$a↓k | 1 ≤ k
≤ n\}\cr
\3skip \{x\}\quad ⊗$in contexts where a real value, not a set,
is\cr
⊗required, denotes fractional part: $x$ mod 1⊗ 3.3.3\cr
\3skip $[y, z)\quad ⊗$half-open interval: $\{x | y ≤ x < z\}\cr
\3skip \parallel S\parallel \quad ⊗$cardinal: number of elements
in set $S\cr
\3skip \biglp (x)\bigrp \quad ⊗$sawtooth function⊗ 3.3.3\cr
\3skip $|x|\quad ⊗$absolute value of $x: (x < 0 \dblrtarrow
-x; x)\cr
\-3skip \lfloor x\rfloor \quad ⊗$floor of $x$, greatest integer
function: \mathop{max??$|raise2 k≤x?? k⊗ 1.2.4\cr
\3skip x$ mod $y\quad ⊗$mod function: $(y = 0 \dblrtarrow x;
x - y\lfloor x/y\rfloor )⊗ 1.2.4⊗u?????????|newtype$ W58320---Computer
Programming\quad (Knuth/Addison-Wesley)\quad Appendix\quad f.
84
%folio 849 galley 13 (C) Addison-Wesley 1978
9\quad g. 13d
$$|newtype |tab \qquad \qquad \qquad \qquad \quad |tab \qquad
\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad
|tab \qquad \qquad \quad |tab |zfa ⊗⊗⊗{\bf Section}\cr
{\bf Formal symbolism} ⊗{\bf Meaning}⊗{\bf reference}\cr
\-2skip |linerule \6skip ⊗⊗{\bf Section}\cr
{\bf Formal symbolism} ⊗{\bf Meaning}⊗{\bf reference}\cr
\-2skip |linerule \6skip ⊗⊗{\bf Section}\cr
{\bf Formal symbolism} ⊗{\bf Meaning}⊗{\bf reference}\cr
\-2skip |linerule \6skip ⊗⊗{\bf Section}\cr
{\bf Formal symbolism} ⊗{\bf Meaning}⊗{\bf reference}\cr
\-2skip |linerule $u(x)$mod $v(x)\quad ⊗$remainder of polynomial
$u(x)$ divided by $v(x)⊗ 4.6.1\cr
\3skip x ≡ y\modulo z\quad ⊗$relation of congruence: $x$
mod $z = y$ mod $z⊗ 1.2.4\cr
\3skip$ log$↓b x\quad ⊗$logarithm, base $b$, of $x$ (real positive
$b ≠ 1):\cr
⊗x = b$$↑{log}|infsup b↑x⊗ 1.2.2\cr
\3skip$ lg $x\quad ⊗$binary logarithm: log$↓2 x⊗ 1.2.2\cr
\3skip$ ln $x\quad ⊗$natural logarithm: log$↓e x⊗ 1.2.2\cr
\3skip$ exp $x\quad ⊗$exponential of $x: e↑x⊗ 1.2.2\cr
\3skip \langle X↓n\rangle \quad ⊗$the infinite sequence $X↓0,
X↓1, X↓2, . . $. (here $n\cr
⊗$is a letter that is part of the symbol)⊗ 1.2.9\cr
\3skip $f↑\prime (x)\quad ⊗$derivative of $f$ at $x⊗ 1.2.9\cr
\3skip f↑{\prime\prime}(x)\quad ⊗$second derivative of $f$ at $x⊗ 1.2.10\cr
\3skip f↑{(n)}(x)\quad ⊗n$th derivative: $\biglp n = 0 \dblrtarrow
f(x);\cr
\3skip ⊗g↑\prime (x)\qquad$ where\qquad $g(x) = f↑{(n-1)}(x)\bigrp
⊗ 1.2.11.2\cr
\-3skip H↑{(x)}↓{n}\quad ⊗1 + 1/2↑x + \cdots + 1/n↑x = \sum
↓{1≤k≤n} 1/k↑x⊗ 1.2.7\cr
\3skip H↓n\quad ⊗$harmonic number: $H↑{(1)}↓{n}⊗ 1.2.7\cr
\3skip F↓n\quad ⊗$Fibonacci number:\cr
⊗\3skip$ (n ≤ 1 \dblrtarrow n; F↓{n-1} + F↓{n-2})⊗ 1.2.8\cr
\3skip B↓n\quad ⊗$Bernoulli number⊗ 1.2.11.2\cr
\3skip B($x, y)\quad ⊗$Beta function⊗ 1.2.6\cr
\3skip sign($x)\quad ⊗$sign of $x:\cr
\3skip ⊗\biglp x = 0 \dblrtarrow 0; (x > 0 \dblrtarrow +1; -1)\bigrp \cr
\3skip \delta (x)\quad ⊗$characteristic function of the integers⊗
3.3.3\cr
\3skip $\zeta (x)\quad ⊗$zeta function: $H↑{(x)}↓{∞}$ when $x
> 1⊗ 1.2.7\cr
\3skip \Gamma (x)\quad ⊗$gamma function: $\gamma (x, ∞); (x
- 1)!$ when $x\cr
⊗$is a positive integer⊗ 1.2.5\cr
\3skip $\gamma (x, y)\quad ⊗$incomplete gamma function⊗ 1.2.11.3\cr
\3skip $\gamma \quad ⊗$Euler's constant⊗ 1.2.7\cr
\-3skip $e\quad ⊗$base of natural logarithms: $\sum ↓{k≥0} 1/k!⊗
1.2.2\cr
\3skip ∞\quad ⊗$infinity: larger than any number\cr
\3skip |spose /0\quad ⊗empty set (set with no elements)\cr
\3skip $\phi \quad ⊗$golden ratio, ${1\over 2}$(1 + \sqrt{5})⊗
1.2.8\cr
\-3skip $\varphi (n)\quad ⊗$Euler's totient function: $\sum
↓{0≤k<n??$gcd($k,n)=1}1⊗ 1.2.4\cr
\3skip \mu (n)\quad ⊗$M|spose 4obius function⊗ 4.5.2\cr
\3skip $??(n)\quad ⊗$von Mangoldt's function⊗ 4.5.3\cr
\3skip $p(n)\quad ⊗$number of partitions of $n⊗ 1.2.1\cr
\3skip$ Pr\biglp $S(n)\bigrp \quad ⊗$probability that statement
$S(n)$ is true, for\cr
⊗``random'' $n⊗ 3.5, 4.2.4\cr
\3skip O\biglp f(n)\bigrp \quad ⊗$big-oh of $f(n)$ as $n → ∞⊗
1.2.11.1\cr
\3skip O\biglp f(x)\bigrp \quad ⊗$big-oh of $f(x)$, for small
$x$ (or for $x$ in some\cr
⊗specified range)⊗ 1.2.11.1\cr
\3skip \quad (min $x↓1$, ave $x↓2,\quad ⊗$a random variable
having minimum value $x↓1,\cr$
max $x↓3, dev x↓4)\quad ⊗$average (``expected'') value $x↓2$,
maximum\cr
⊗value $x↓3$, standard deviation $x↓4⊗ 1.2.10\cr
\3skip$ mean($g)\quad ⊗$mean value of probability distribution
repre-\cr
⊗sented by generating function $g: g↑\prime (1)⊗ 1.2.10\cr
\3skip$ var($g)\quad ⊗$variance of probability distribution
repre-\cr
⊗sented by generating function $g:\cr
\6skip ⊗g↑{\prime\prime}(1) + ↑\prime (1) - g↑\prime (1)↑2⊗ 1.2.10\cr
\6skip$ deg($u)\quad ⊗$degree of polynomial $u⊗ 4.6\cr
\3skip ??3(u)\quad ⊗$leading coefficient of polynomial $u⊗ 4.6\cr
\3skip$ cont($u)\quad ⊗$content of polynomial $u⊗ 4.6.1\cr
\3skip$ pp\biglp $u(x)\bigrp \quad ⊗$primitive part of polynomial
$u$, evaluated\cr
⊗at $x⊗ 4.6.1\cr
\3skip ??R(w)\quad ⊗$real part of complex number $w\cr
\3skip ??I(w)\quad ⊗$imaginary part of complex number $w\cr
\3skip |spose 3w\quad ⊗$complex conjugate: $??R(w) - ??I(w)\cr
\3skip ⊗$end of algorithm, program, or proof⊗ 1.1\cr
\3skip | |\quad ⊗one blank space⊗ A.1\cr
\3skip rA\quad ⊗register A (accumulator) of \MIX⊗ A.1\cr
\3skip rX\quad ⊗register X (extension) of \MIX⊗ A.1\cr
\3skip rI1, \ldotss , rI6\quad ⊗(index) registers I1, \ldotss
, I6 of \MIX⊗ A.1\cr
\3skip rJ\quad ⊗(jump) register J of \MIX⊗ A.1\cr
\3skip (L:R)\quad ⊗partial field of \MIX\ word, 0 ≤ L ≤ R ≤ 5⊗
A.1\cr
\3skip OP ADDRESS,I(F)\quad ⊗notation for \MIX\ instruction⊗ A.1,
A.2\cr
\3skip $u\quad ⊗$unit of time in \MIX⊗ A.1\cr
\3skip |raiseordrop ??\quad ⊗``self'' in \.{MIXAL}⊗ A.2\cr
\3skip 0F, 1F, 2F, \ldotss , 9F\quad ⊗``forward'' local symbol
in \.{MIXAL}⊗ A.2\cr
\3skip 0B, 1B, 2B, \ldotss , 9B\quad ⊗``backward'' local symbol
in \.{MIXAL}⊗ A.2\cr
\3skip 0H, 1H, 2H, \ldotss {\bf }, 9H\quad ⊗``here'' local symbol
in \.{MIXAL}⊗ A.2\cr
u??????????????\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad